Dijkstra's algorithmEdexcel International A Level Maths: Mind map

Exam questions on Dijkstra's algorithm

1. A network has five vertices $S$, $A$, $B$, $C$ and $T$. The arcs and their lengths are $SA=9$, $SB=5$, $AB=3$, $AC=10$, $BC=2$, $BT=9$ and $CT=6$. Dijkstra's algorithm is applied starting at $S$.
   Find the shortest route from $S$ to $A$ and its length. Explain why the arc $SA$ is not used.2 marks
2. A network has six vertices $A$ to $F$. The arcs and their lengths are $AB=2$, $AC=8$, $AD=9$, $BC=13$, $BE=5$, $CD=13$, $CE=14$, $DF=6$ and $EF=4$. Dijkstra's algorithm is applied starting at $A$.
   Find the shortest route from $A$ to $F$ and state its length.2 marks
3. A courier company has six depots $A$ to $F$. The direct roads between depots and their lengths in km are $AB=4$, $AC=3$, $AD=11$, $BC=10$, $BE=5$, $CD=13$, $CE=7$, $DF=13$ and $EF=12$. A courier travels from $A$ to $F$.
   Use Dijkstra's algorithm to find the shortest route from $A$ to $F$. State the order in which the vertices are permanently labelled, with their final labels, and the length of the route.3 marks