Shortest paths with Dijkstra’s algorithm

What you’ll learn

• Update temporary labels and make permanent choices.
• Recover a shortest path using predecessor information.
• Respect edge directions and non-negative weights.

Understand the idea

Dijkstra's algorithm finds shortest distances from a source in a network with non-negative edge weights. Label the source 0 and other vertices infinity. Make the smallest temporary label permanent, then use its outgoing edges to improve labels of its unselected neighbours.

When considering an edge from $u$ to $v$, compare the old label at $v$ with the permanent distance to $u$ plus the edge weight. Keep the smaller value and record the predecessor if the label improves. A shortest path is recovered by tracing predecessors backwards from the destination.

An undirected edge can be traversed either way; a directed arc must be followed in its stated direction. Ties can lead to more than one shortest path. Once the target is permanently labelled, its distance is settled, although continuing is necessary if all source-to-vertex distances are requested.

Key formulae

$$d(s)=0,\qquad d(v)=\infty\ (v\ne s)$$

$$d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\}$$

$$\text{path length}=\sum_{e\in\text{path}}w(e)$$

Worked example

An undirected network has exactly edges AB = 4, AC = 2, CB = 1, BD = 5, CD = 8, CE = 10, DE = 2. Find a shortest path from A to E using Dijkstra’s algorithm.

1. Fix A at 0. Its temporary labels give C = 2 and B = 4.
2. Fix C at 2; improve B to 3 and label D = 10 and E = 12.
3. Fix B at 3; improve D to 8. Fix D at 8; improve E to 10.
4. Fix E at 10. Following predecessors gives E ← D ← B ← C ← A.

Answer: A–C–B–D–E has length 10.