-
Notifications
You must be signed in to change notification settings - Fork 4
/
dijkstra.py
79 lines (62 loc) · 2.33 KB
/
dijkstra.py
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import pqdict
def dijkstra(graph, source, target=None):
"""
Computes the shortests paths from a source vertex to every other vertex in
a graph
"""
# The entire main loop is O( (m+n) log n ), where n is the number of
# vertices and m is the number of edges. If the graph is connected
# (i.e. the graph is in one piece), m normally dominates over n, making the
# algorithm O(m log n) overall.
dist = {}
pred = {}
# Store distance scores in a priority queue dictionary
pq = pqdict.PQDict()
for node in graph:
if node == source:
pq[node] = 0
else:
pq[node] = float('inf')
# Remove the head node of the "frontier" edge from pqdict: O(log n).
for node, min_dist in pq.iteritems():
# Each node in the graph gets processed just once.
# Overall this is O(n log n).
dist[node] = min_dist
if node == target:
break
# Updating the score of any edge's node is O(log n) using pqdict.
# There is _at most_ one score update for each _edge_ in the graph.
# Overall this is O(m log n).
for neighbor in graph[node]:
if neighbor in pq:
new_score = dist[node] + graph[node][neighbor]
if new_score < pq[neighbor]:
pq[neighbor] = new_score
pred[neighbor] = node
return dist, pred
def shortest_path(graph, source, target):
dist, pred = dijkstra(graph, source, target)
end = target
path = [end]
while end != source:
end = pred[end]
path.append(end)
path.reverse()
return path
if __name__=='__main__':
# A simple edge-labeled graph using a dict of dicts
graph = {'a': {'b':1, 'c':9999},
'b': {'a':9999, 'c':1},
'c': {'a':1, 'b':1}}
print "shortest_path(g, a, b) = ",
print shortest_path(graph, 'a', 'b')
print "shortest_path(g, a, c) = ",
print shortest_path(graph, 'a', 'c')
print "shortest_path(g, b, a) = ",
print shortest_path(graph, 'b', 'a')
print "shortest_path(g, b, c) = ",
print shortest_path(graph, 'b', 'c')
print "shortest_path(g, c, a) = ",
print shortest_path(graph, 'c', 'a')
print "shortest_path(g, c, b) = ",
print shortest_path(graph, 'c', 'b')