Dijkstra: shortest paths with weights
In lesson 7-2, BFS found shortest paths when every edge cost 1. Give edges weights (minutes, dollars, distance) and BFS breaks: fewest edges is no longer cheapest. A → B directly might cost 4 while A → C → B costs 1 + 2 = 3.
Dijkstra's algorithm fixes BFS with one substitution: replace the queue with a min-heap (priority queue, from Data Structures) keyed by total distance from the start.
Why a heap: BFS's plain queue processes nodes in discovery order, but with weights, the next node that can be finalized is the one with the smallest total distance so far — exactly the question a min-heap answers in O(log n). The loop:
- Pop the unvisited node with the smallest known distance. That distance is now final, nothing can beat it, because any other route would have to pass through something already farther.
- Relax its neighbors: if going through this node is shorter than their best known distance, update them and push.
If you want a picture: pour water into the start node and it spreads along the pipes, wetting nodes in order of true distance — that is precisely the order the heap pops them.
Requirement: no negative edge weights, or step 1's promise breaks.
Code exercise · python
Run this. The heap always surfaces the closest unfinished node. Watch B: it first gets a tentative distance of 4 (direct road), then improves to 3 via C. The stale (4, "B") heap entry is skipped by the d > dist check.
Quiz
Why does plain BFS give wrong answers on weighted graphs?
Code exercise · python
Your turn, the classic wrapper: a signal starts at one node and takes dist[n] time to reach node n. network_delay returns the time until ALL nodes have it, or -1 if some node is unreachable. dijkstra is given.
Problem
A map has non-negative travel times on its roads and you need the fastest route between two cities. Which algorithm: BFS, DFS, or Dijkstra?