Skip to content

Instantly share code, notes, and snippets.

@kachayev
Last active January 9, 2023 14:58
Embed
What would you like to do?
Dijkstra shortest path algorithm based on python heapq heap implementation
from collections import defaultdict
from heapq import *
def dijkstra(edges, f, t):
g = defaultdict(list)
for l,r,c in edges:
g[l].append((c,r))
q, seen, mins = [(0,f,())], set(), {f: 0}
while q:
(cost,v1,path) = heappop(q)
if v1 not in seen:
seen.add(v1)
path = (v1, path)
if v1 == t: return (cost, path)
for c, v2 in g.get(v1, ()):
if v2 in seen: continue
prev = mins.get(v2, None)
next = cost + c
if prev is None or next < prev:
mins[v2] = next
heappush(q, (next, v2, path))
return float("inf"), None
if __name__ == "__main__":
edges = [
("A", "B", 7),
("A", "D", 5),
("B", "C", 8),
("B", "D", 9),
("B", "E", 7),
("C", "E", 5),
("D", "E", 15),
("D", "F", 6),
("E", "F", 8),
("E", "G", 9),
("F", "G", 11)
]
print "=== Dijkstra ==="
print edges
print "A -> E:"
print dijkstra(edges, "A", "E")
print "F -> G:"
print dijkstra(edges, "F", "G")
@xdavidliu
Copy link

pretty sure this is not Dijkstra; you're doing heappush(q, (next, v2, path)) at the very end, but in True dijkstra it would need a call to "decrease_key", which in python is heap._siftdown

@chausen
Copy link

chausen commented Feb 27, 2022

@xdavidliu I was confused by this until I saw https://stackoverflow.com/a/31123108. I think Dijkstra's algorithm is a higher level concept, so either implementation is valid.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment