Shortest Paths
Choose the frontier rule that preserves minimum path cost under edge weights.
The idea
Dijkstra grows a shortest-path tree from a source by always finalising the closest unsettled vertex (via a min-heap) and relaxing its edges. It requires non-negative weights; negative edges need Bellman-Ford.
The visualization keeps three structures in sync: the tentative-distance array, the priority queue of candidates, and the settled tree drawn on the graph — so you can see exactly why the greedy 'closest first' choice is safe.
GPS navigation: repeatedly expand the cheapest-so-far frontier of intersections until the destination is finalised.
When to reach for it
- Weighted shortest path with non-negative edges.
- Cheapest cost / minimum effort paths.
- Network latency / routing.
Language-independent template
dist = {src: 0}; pq = [(0, src)]
while pq:
d, u = heappop(pq)
if d > dist[u]: continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w; heappush(pq, (dist[v], v))Complexity — time O(E log V), space O(V).
Common mistakes
- Using Dijkstra with negative weights.
- Not skipping stale heap entries.
- Forgetting to record finalised distances.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Determine whether any route connects source and destination.
Find when a signal from one node reaches every directed node.
Minimize the maximum elevation encountered on a route across a grid.