FilesExpand file tree

 master

/

dijkstra_algorithm.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (37 loc) · 1.66 KB

 master

/

dijkstra_algorithm.py

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (37 loc) · 1.66 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

#!/usr/bin/env python

#coding:utf-8

"""

最短路径问题的Dijkstra算法

是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

这个算法的python实现途径很多，网上能够发现不少。这里推荐一个我在网上看到的，本来打算自己写，看了这个，决定自己不写了，因为他的已经太好了。

"""

# Dijkstra's algorithm for shortest paths

# David Eppstein, UC Irvine, 4 April 2002

# code source:http://www.algolist.com/code/python/Dijkstra%27s_algorithm

from priodict import priorityDictionary

def Dijkstra(G,start,end=None):

D = {} # dictionary of final distances

P = {} # dictionary of predecessors

Q = priorityDictionary() # est.dist. of non-final vert.

Q[start] = 0

for v in Q:

D[v] = Q[v]

if v == end: break

for w in G[v]:

vwLength = D[v] + G[v][w]

if w in D:

if vwLength < D[w]:

raise ValueError, "Dijkstra: found better path to already-final vertex"

elif w not in Q or vwLength < Q[w]:

Q[w] = vwLength

P[w] = v

return (D,P)

def shortestPath(G,start,end):

D,P = Dijkstra(G,start,end)

Path = []

while 1:

Path.append(end)

if end == start: break

end = P[end]

Path.reverse()

return Path