Dijkstra's algorithmEdexcel A-Level Further Maths: Subtopic test

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

   (a)

   What is the final label of vertex $B$?

   [1 mark]

   • A$7$
   • B$2$
   • C$6$
   • D$9$

   (b)

   Which is the shortest route from $S$ to $T$ and its length?

   [1 mark]

   • A$S-B-D-T$, 19 km
   • B$S-A-C-T$, 18 km
   • C$S-B-C-T$, 18 km
   • D$S-A-B-C-T$, 17 km

   (c)

   Explain why the final label at $B$ is 6 and not 7.

   [2 marks]

   Total for question 1: 4 marks

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

   (a)

   Counting $A$ as the first, which vertex receives the fourth permanent label?

   [1 mark]

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

   (b)

   What is the final label of $F$?

   [1 mark]

   • A$21$
   • B$20$
   • C$23$
   • D$24$

   (c)

   Use the labels to find the shortest route from $A$ to $F$ and show how you worked it out.

   [2 marks]

   Total for question 2: 4 marks

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

   (a)

   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]

   (b)

   A courier must travel from $S$ to $T$ and must call at $X$. Find the shortest such route and its length.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A delivery network has eight vertices $S$, $A$, $B$, $C$, $D$, $E$, $F$ and $T$. The roads and their lengths in km are $SD=3$, $SF=6$, $AB=17$, $AD=14$, $AT=13$, $BC=15$, $BD=9$, $BE=8$, $BF=11$, $BT=16$, $CF=18$, $EF=19$ and $ET=2$.

   (a)

   Use Dijkstra's algorithm to find the shortest route from $S$ to $T$. Give the vertices in the order they are labelled, with their final labels, and state the route and its length.

   [6 marks]

   (b)

   The road $BE$ is closed. Explain why the labels of $D$, $F$, $B$ and $A$ do not change, find the new shortest route from $S$ to $T$, and state how much longer it is.

   [6 marks]

   Total for question 4: 12 marks

End of questions