Dijkstra's algorithmEdexcel A-Level Further Maths: Mind map

Exam questions on Dijkstra's algorithm

1. A road network joins a depot $S$ to a warehouse $T$ through four junctions $A$, $B$, $C$ and $D$. The roads and their lengths in km are $SA=4$, $SB=7$, $AB=2$, $AC=6$, $BC=3$, $BD=8$, $CD=6$, $CT=8$ and $DT=4$. Dijkstra's algorithm is used to find the shortest route from $S$ to $T$.
   Explain why the final label at $B$ is 6 and not 7.2 marks
2. Six towns $A$ to $F$ are joined by roads with lengths in km: $AB=5$, $AC=8$, $BC=2$, $BD=9$, $CD=4$, $CE=9$, $DE=3$, $DF=10$ and $EF=6$. Dijkstra's algorithm is used starting from $A$.
   Use the labels to find the shortest route from $A$ to $F$ and show how you worked it out.2 marks
3. A courier network has seven vertices $S$, $A$, $B$, $C$, $D$, $X$ and $T$. The roads and their lengths in km are $SA=8$, $SC=12$, $AC=3$, $AX=11$, $BC=2$, $BD=6$, $BT=10$, $CD=7$, $CT=5$, $DX=9$ and $XT=4$.
   Apply Dijkstra's algorithm from $S$. Show the working values at $C$, and state the permanent labels of the next three vertices to be labelled after $S$.3 marks