Dijkstra’s Algorithm
Interactive visualizations for Chapter 10 of the Ricerca Operativa notes
The Graph
We work with a directed weighted graph of 7 nodes and 11 arcs throughout this chapter.
- Nodes: s, a, b, c, d, e, t
- Arcs (with weights): s→a(4), s→b(2), a→c(3), a→d(2), b→d(3), b→e(8), c→e(5), c→t(6), d→e(1), d→t(5), e→t(1)
Dijkstra Algorithm Trace
Dijkstra’s algorithm maintains a priority queue ordered by tentative distance. At each step it extracts the minimum-distance unsettled node, relaxes its outgoing arcs, and moves the node to the settled set T.
| Step | Extract | Process | Updates | Settled T after |
|---|---|---|---|---|
| 0 | s (d=0) | — | d[a]=4, d[b]=2 | {s} |
| 1 | b (d=2) | b | d[d]=5, d[e]=10 | {s, b} |
| 2 | a (d=4) | a | d[c]=7, d[d]=min(5,6)=5 | {s, b, a} |
| 3 | d (d=5) | d | d[e]=min(10,6)=6, d[t]=10 | {s, b, a, d} |
| 4 | e (d=6) | e | d[t]=min(10,7)=7 | {s, b, a, d, e} |
| 5 | c (d=7) | c | d[t]=min(7,13)=7 (no change) | {s, b, a, d, e, c} |
| 6 | t (d=7) | t | — | {s, b, a, d, e, c, t} |
Priority Queue Evolution
The chart below shows how the tentative distance d[v] evolves for each node across iterations, and the step at which each node is finalized (extracted from the priority queue).
Shortest Path Tree
After Dijkstra terminates, the predecessor pointers form the shortest-path tree rooted at s. The optimal path from s to t is highlighted in orange.
Predecessor map: pred[a]=s, pred[b]=s, pred[c]=a, pred[d]=b, pred[e]=d, pred[t]=e
Optimal Path Walkthrough
The shortest path from s to t has total cost 7, following s → b → d → e → t.
Why Non-Negative Weights Matter
Dijkstra’s algorithm relies on the greedy correctness property: once a node is settled, its distance cannot decrease further. This holds only when all arc weights are non-negative.
If a negative arc exists, a later path through an unsettled node might yield a smaller distance to an already-settled node — breaking the algorithm’s guarantee.
Counterexample: s→a(2), s→b(5), b→a(−4)
- Dijkstra settles a first with d[a]=2 (via s→a).
- But the true shortest path is s→b→a with cost 5+(−4)=1.
- Dijkstra gives the wrong answer d[a]=2 instead of 1.
Key takeaway: For graphs with negative arc weights, use the Bellman–Ford algorithm (O(VE)), which handles negative weights but not negative cycles. Dijkstra remains the algorithm of choice when all weights are non-negative, running in O((V + E) log V) with a binary heap.