Skip to content

Instantly share code, notes, and snippets.

@hanfang
hanfang / shortestPath.py
Last active November 11, 2023 22:09
Finding the shortest path in a weighted DAG with Dijkstra in Python and heapq
import collections
import heapq
def shortestPath(edges, source, sink):
# create a weighted DAG - {node:[(cost,neighbour), ...]}
graph = collections.defaultdict(list)
for l, r, c in edges:
graph[l].append((c,r))
# create a priority queue and hash set to store visited nodes
queue, visited = [(0, source, [])], set()