Dijkstra Shortest Path
Explain Dijkstra's algorithm and implement shortest distances from a source in a weighted directed graph with non-negative weights.
Answers use simple, clear English.
Quick interview answer
Priority queue of (dist, node). Pop the smallest unsettled distance, relax outgoing edges, push improved distances. Non-negative weights required; negative edges need Bellman-Ford.
Detailed answer
Priority queue of (dist, node). Pop the smallest unsettled distance, relax outgoing edges, push improved distances. Non-negative weights required; negative edges need Bellman-Ford. Decrease-key vs push-duplicate are both common; discuss complexity with binary heap.
Full explanation
Decrease-key vs push-duplicate are both common; discuss complexity with binary heap.
Real example & use case
Maps routing between intersections with road travel times as weights.
Pros & cons
Pros: efficient for non-negative weights. Cons: fails with negatives; denser graphs may prefer other algos.
Code example
import heapq
from collections import defaultdict
def dijkstra(n: int, edges: list[tuple[int,int,int]], src: int) -> list[float]:
g = defaultdict(list)
for u, v, w in edges:
g[u].append((v, w))
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 g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return distPractice code · python (view only · no execution)
import heapq
from collections import defaultdict
def dijkstra(n: int, edges: list[tuple[int,int,int]], src: int) -> list[float]:
g = defaultdict(list)
for u, v, w in edges:
g[u].append((v, w))
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 g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist