Dijkstra's algorithmEdexcel International A Level Maths: Revision notes

In a network each arc has a weight, such as a distance, time or cost. The shortest path problem asks for the path between two vertices with the least total weight. Trying every path becomes impractical as the network grows, so we use Dijkstra's algorithm. Dijkstra's algorithm works from a start vertex and finds the shortest distance to every vertex, labelling them in order of increasing distance. It can be stopped as soon as the target vertex is permanently labelled. It works for any network with positive weights.

Give each vertex a box with three parts: the order of labelling, the final value and the working values.

1. Give the start vertex the order of labelling 1 and the final value $0$.
2. For each vertex joined to the vertex just labelled, work out (final value $+$ arc weight). Write this as a working value if it is smaller than any working value already there.
3. Choose the vertex with the smallest working value that is not yet permanently labelled. Make that value its final value and give it the next order number.
4. Repeat steps 2 and 3 until the target vertex is labelled. Working values that are replaced by smaller ones are crossed out but kept, so the working can be checked.

Arcs $SA=4$, $SB=2$, $AB=1$, $AT=6$, $BT=8$. Start at $S$ with final value $0$.

• From $S$: working values $A=4$, $B=2$. The smallest is $B$, so $B=2$ is permanent (order 2).
• From $B$: $A=2+1=3$, replacing $4$; $T=2+8=10$. The smallest is $A$, so $A=3$ is permanent (order 3).
• From $A$: $T=3+6=9$, replacing $10$. $T=9$ is permanent (order 4). The shortest distance from $S$ to $T$ is $9$.

The final values give the length, but you must also give the route. Work backwards from the target. At each vertex, look at its neighbours and choose the one for which $\text{final value of vertex}-\text{arc weight}=\text{final value of neighbour}.$ In the worked example, from $T=9$: $9-6=3=A$, so go to $A$. From $A=3$: $3-1=2=B$, so go to $B$. From $B=2$: $2-2=0=S$. The route is $S$-$B$-$A$-$T$. The route is written from the start to the target, with the total length. Using the arc $SA$ ($4$) directly would give $A=4$, which is longer than $3$ via $B$.

If a road is closed, remove that arc and repeat the algorithm. Any vertex whose shortest route did not use that arc keeps its final value. If a new arc of weight $x$ joins vertices $X$ and $Y$, it improves the route to $T$ only when $d(S,X)+x+d(Y,T)<\text{current shortest length},$ where $d$ is the shortest distance, found from the algorithm. This gives an inequality for $x$. Checks: final values must increase in order of labelling, and the final value at each vertex must be no more than any route you can find by inspection.