Shortest Path Algorithm¶

Definition¶

For nonnegative edge lengths, the course's shortest path algorithm sets $d(s)=0$ and $U=\{s\}$ ${s}$ . Repeatedly choose an edge $u-v$ with $u\in U$ $U$ , $v\notin U$ minimizing

d(u)+\ell_{uv}.

Set $d(v)$ equal to this value, record predecessor $u$ , and add $v$ to $U$ . Stop when the destination is added, or continue to obtain distances to all vertices.

Interpretation¶

Vertices enter the settled set $U$ in order of their shortest distance from the origin $s$ . A label $d(v)$ is final as soon as $v$ enters $U$ , and the recorded predecessors recover the actual route after the distance has been computed.

A weighted network from A to F with each vertex labelled by its shortest distance from A, from d(A) = 0 to d(F) = 13, and the shortest-path tree highlighted.

The labels give the shortest distance from $A$ to each vertex; the vertices are settled in the order $A,C,B,D,E,F$ , with $d=0,2,3,8,10,13$ $0, 2, 3, 8, 10, 13$ . The label of $B$ is $3$ , via $C$ , not $4$ via the direct edge: once $d(C)=2$ is known, the edge $C-B$ offers $2+1=3$ $3$ . The red edges are the recorded predecessor edges, and following them back from $F$ gives the route $A-C-B-D-E-F$ of the shortest path problem.

The settled order is correct because lengths are nonnegative. Any other route to the newly chosen vertex $v$ must leave $U$ through some edge, so it already costs at least the smallest candidate value $d(v)$ , and further nonnegative edges cannot make it shorter. With a negative length this breaks down: if $A-B$ has length 2, $A-C$ length 3 and $C-B$ length $-2$ , the algorithm settles $B$ with $d(B)=2$ $2$ , yet the route $A-C-B$ has length 1.

The Dijkstra-Prim method for minimum spanning trees grows its set $U$ in the same way but compares only the edge length $\ell_{uv}$ , not $d(u)+\ell_{uv}$ $ℓ_{uv}$ . In the figure both rules happen to select the same edges, but in general a shortest-path tree and a minimum spanning tree differ.

Key Results¶

Compare complete distances from the origin, not just individual edge lengths.
Ties can be broken arbitrarily when one shortest path is sufficient.
Backtrack from the destination through predecessors and reverse the sequence.

Examples¶

The figure settles vertices in the order $A,C,B,D,E,F$ . The recorded predecessor edges form a shortest-path tree rooted at $A$ .

In the course's worked example with origin $S$ and destination $T$ (a different network from the figure), the labels are $d(B)=2$ $2$ , $d(A)=3$ $3$ , $d(D)=6$ $6$ , $d(C)=7$ $7$ , $d(E)=8$ $8$ , $d(T)=12$ $12$ .
The predecessor chain $T,E,D,A,B,S$ recovers the route of length 12.

Prerequisites¶

Shortest Path Problem

Sources¶

OR Modelling · Week 4

Aliases: Dijkstra's shortest path algorithm Symbols: element of

Last updated: 27 October 2026 11:52