Skip to content

Instantly share code, notes, and snippets.

Last active November 29, 2023 10:21
Star You must be signed in to star a gist
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:
q, seen, mins = [(0,f,())], set(), {f: 0}
while q:
(cost,v1,path) = heappop(q)
if v1 not in seen:
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")
Copy link

alelom commented Jun 9, 2020

I just care for what is right. If I were the lecturer, I'd quote the real author and the source – an action that does not diminish the teaching potential, and encourages sharing of good code lawfully.

Copy link

Thank you so much for this gift, very clean and clever solution 😄

If anyone just wonders how to easily receive as output only the value of the solution remove the cost from the return at line 15:

if v1 == t: return cost
instead of
if v1 == t: return (cost, path)

Copy link

konmaz commented Nov 6, 2020

Nice and clean

Copy link

Thank you very much for this beautiful algorithm.

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

Copy link

chausen commented Feb 27, 2022

@xdavidliu I was confused by this until I saw 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