Dijkstra's algorithmEdexcel International A Level Maths: Subtopic test

1. 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$.

   (a)

   Which vertex is permanently labelled third, counting $S$ as the first?

   [1 mark]

   • A$A$
   • B$B$
   • C$T$
   • D$C$

   (b)

   What is the length of the shortest route from $S$ to $T$?

   [1 mark]

   • A$13$
   • B$14$
   • C$20$
   • D$25$

   (c)

   Find the shortest route from $S$ to $A$ and its length. Explain why the arc $SA$ is not used.

   [2 marks]

   Total for question 1: 4 marks

2. 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$.

   (a)

   Which vertex is permanently labelled fourth, counting $A$ as the first?

   [1 mark]

   • A$B$
   • B$C$
   • C$D$
   • D$E$

   (b)

   What is the shortest distance from $A$ to $D$?

   [1 mark]

   • A$8$
   • B$17$
   • C$9$
   • D$21$

   (c)

   Find the shortest route from $A$ to $F$ and state its length.

   [2 marks]

   Total for question 2: 4 marks

3. 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$.

   (a)

   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]

   (b)

   A new road is built directly between $C$ and $F$ of length $x$ km. Find the greatest integer value of $x$ for which the new road makes the shortest distance from $A$ to $F$ shorter than it is at present.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network of roads joins seven towns $S$, $A$, $B$, $C$, $D$, $E$ and $T$. The roads and their lengths in km are $SA=9$, $SB=8$, $SC=15$, $AB=14$, $AD=11$, $BC=5$, $BE=7$, $CD=4$, $CE=14$, $DE=5$, $DT=6$ and $ET=10$. An emergency vehicle must travel from $S$ to $T$ by the shortest route.

   (a)

   Use Dijkstra's algorithm to find the shortest route from $S$ to $T$. State the order in which vertices are permanently labelled, with their final values, show where any working value is replaced, and give the route and its length.

   [6 marks]

   (b)

   The road $CD$ is closed for repairs. Find the new shortest route from $S$ to $T$, and the extra distance the vehicle must now travel.

   [6 marks]

   Total for question 4: 12 marks

End of questions