Single-source shortest paths on non-negative weighted graphs using a priority queue.
Maintain tentative distances and relax edges by always expanding the node with the smallest current distance (min-heap).
Use on graphs with non-negative weights for shortest paths; prefer 0-1 BFS for 0/1 weights or Bellman-Ford if negatives exist.
Initialize distances to ∞, push (0, src) to a min-heap, pop best and relax neighbors; skip if popped distance is stale.
Use this pattern when use on graphs with non-negative weights for shortest paths; prefer 0-1 bfs for 0/1 weights or bellman-ford if negatives exist.
import heapq
def dijkstra(n, adj, src):
dist=[float('inf')]*n; dist[src]=0
pq=[(0,src)]
while pq:
d,u=heapq.heappop(pq)
if d!=dist[u]: continue
for v,w in adj[u]:
nd=d+w
if nd<dist[v]: dist[v]=nd; heapq.heappush(pq,(nd,v))
return distTypical implementation with a min-priority queue.
import heapq
def dijkstra(n, adj, src):
dist=[float('inf')]*n; dist[src]=0
pq=[(0,src)]
while pq:
d,u=heapq.heappop(pq)
if d!=dist[u]: continue
for v,w in adj[u]:
nd=d+w
if nd<dist[v]: dist[v]=nd; heapq.heappush(pq,(nd,v))
return distPick by weight type: unweighted→BFS, {0,1}→0-1 BFS, non-negative→Dijkstra
import heapq
def dijkstra(n, adj, src):
dist=[float('inf')]*n; dist[src]=0
pq=[(0,src)]
while pq:
d,u=heapq.heappop(pq)
if d!=dist[u]: continue
for v,w in adj[u]:
nd=d+w
if nd<dist[v]: dist[v]=nd; heapq.heappush(pq,(nd,v))
return distRelax edges V-1 times; detect negative cycles by an extra pass
def bellman_ford(n, edges, src):
INF=10**18; dist=[INF]*n; dist[src]=0
for _ in range(n-1):
changed=False
for u,v,w in edges:
if dist[u]+w<dist[v]: dist[v]=dist[u]+w; changed=True
if not changed: break
# Optional: detect negative cycle
for u,v,w in edges:
if dist[u]+w<dist[v]: return None # negative cycle
return distEach edge can relax once; heap ops cost log V.
Distance array + heap.