Skip to content

Instantly share code, notes, and snippets.

@amankharwal

amankharwal/dijkstras.py Secret

Created Apr 18, 2021
Embed
What would you like to do?
from heapq import *
from collections import defaultdict
def dijkstra(edges, strat_node, end_node):
g = defaultdict(list)
for start, end, weight in edges:
g[start].append((weight, end))
q, visited = [(0, strat_node,())], set()
while q:
(cost,v1,path) = heappop(q)
if v1 not in visited:
visited.add(v1)
path = (v1, path)
if v1 == end_node:
return (cost, path)
for c, v2 in g.get(v1, ()):
if v2 not in visited:
heappush(q, (cost+c, v2, path))
print (q)
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", 7),
("D", "F", 6),
("E", "F", 8),
("E", "G", 9),
("F", "G", 11)
]
print ("=== Dijkstra ===")
print ("A >> G:")
print (dijkstra(edges, "A", "G"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment