Skip to content

Instantly share code, notes, and snippets.

@yitonghe00
Forked from kachayev/dijkstra.py
Created September 15, 2018 03:16
Show Gist options
  • Save yitonghe00/df2a92af32266791db777a408d600f2b to your computer and use it in GitHub Desktop.
Save yitonghe00/df2a92af32266791db777a408d600f2b to your computer and use it in GitHub Desktop.
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")
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment