Dijkstra's algorithmEdexcel A-Level Further Maths: Revision notes

Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex in a weighted network, or to one chosen target. The weights must not be negative. It is used for routes such as the shortest road distance or the least travel time. Each vertex is drawn as a box (or listed in a table) with four parts:

• the vertex name,
• the order of labelling: 1 for the start, 2 for the next vertex given a permanent label, and so on,
• the final label: the shortest distance from the start,
• the working values that are tried and replaced on the way. A label is permanent once the vertex has been chosen, and it never changes.

1. Give the start vertex the permanent label 0 and order of labelling 1.
2. For each vertex joined to the vertex just labelled, work out its label plus the edge length. If the vertex has no working value, or this value is smaller than its current one, record it as the new working value. Cross out a larger value.
3. Look at all working values at vertices without a permanent label. Choose the smallest, make it permanent, and give the next order of labelling.
4. Repeat steps 2 and 3. Stop when the target has a permanent label, or when every vertex does. The smallest working value is final because every other route to that vertex must pass through a vertex with at least as large a working value, and adding a non-negative weight cannot make it shorter.

Roads: $SA=4$, $SB=7$, $AB=2$, $AC=6$, $BC=3$, $BD=8$, $CD=6$, $CT=8$, $DT=4$. Find the shortest route from $S$ to $T$.

• $S=0$. Working values: $A=4$, $B=7$. Smallest is $A=4$, permanent.
• From $A$: $B=4+2=6$ replaces 7. $C=4+6=10$. Smallest is $B=6$, permanent.
• From $B$: $C=6+3=9$ replaces 10. $D=6+8=14$. Smallest is $C=9$.
• From $C$: $D=9+6=15$ (not better than 14). $T=9+8=17$. Smallest is $D=14$.
• From $D$: $T=14+4=18$ (not better than 17). $T=17$ is permanent. Order of labelling: $S$, $A$, $B$, $C$, $D$, $T$.

The labels give the length. To find the route, work backwards from the target. At each vertex, find the neighbour whose final label plus the edge length equals the label of the vertex you are at. In the example, $T=17=9+8$, so the route comes from $C$; $C=9=6+3$, so from $B$; $B=6=4+2$, so from $A$; and $A=4$ from $S$. The route is $S-A-B-C-T$ with length 17. If a question gives a route from the start labelled by the algorithm, you must show the sums or the working values that justify each step.

• Several targets: the final labels give the shortest distance to every labelled vertex.
• Route through a vertex: if the route must call at $X$, add the shortest distance from the start to $X$ and the shortest distance from $X$ to the target.
• A road closed: vertices labelled before the closed edge was used keep their labels. Repeat from the point where the closed edge mattered, using the next best working values.
• Directed networks: only follow arcs in the direction of the arrow. A vertex's shortest route may leave a long edge unused. Compare all the working values at the target before you stop.