FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/dijkstra_algorithm.py at master · linuxying/algorithm · GitHub
linuxying
algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
dijkstra_algorithm.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
51 lines (37 loc) · 1.66 KB
Breadcrumbs
algorithm
/
dijkstra_algorithm.py
Copy path
File metadata and controls
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
Back
|
FazBrowse Home
|
New Git URL