Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
simple djikstra
import heapq
def djikstra(graph, s, z):
dist = {s:0}
pred = {s:None}
visited = {}
q = []
heapq.heappush(q, s)
while q:
u = heapq.heappop(q)
visited[u] = True
if u == z:
break
for n, c in graph[u]:
if not visited.get(n, False):
if dist.get(n, float('inf')) > dist[u] + c:
dist[n] = dist[u] + c
pred[n] = u
heapq.heappush(q, n)
return dist[z], pred
G = { 'a' : [('b', 6), ('c', 2)],
'b' : [('a', 6), ('c', 3), ('d', 1), ('e', 4)],
'c' : [('a', 2), ('b', 3), ('d', 1)],
'd' : [('c', 1), ('b', 1), ('e', 6)],
'e' : [('b', 4), ('d', 6)]
}
djikstra(G, 'a', 'e')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.