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

1. 1
   A network has four vertices $A$, $B$, $C$ and $D$. The roads and their lengths are $AB=2$, $AC=3$, $BC=7$, $BD=10$ and $CD=4$. Floyd's algorithm is applied, with the pivots in the order $A$, $B$, $C$, $D$. In the distance table the leading diagonal is 0 and a dash means there is no direct road. In the route table, the entry in row $X$, column $Y$ is the first vertex to travel to when going from $X$ to $Y$; initially it is $Y$ itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).

   (a)

   After iteration 1 (pivot $A$), what is the entry in row $B$, column $C$ of the distance table?

   [1 mark]

   • A$7$
   • B$5$
   • C$3$
   • D$2$

   (b)

   After iteration 1, what is the entry in row $B$, column $C$ of the route table?

   [1 mark]

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

   (c)

   Complete the algorithm. Find the shortest distance from $B$ to $D$ and use the final route table to give the route.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Five sites $A$ to $E$ are joined by roads with lengths in km: $AB=5$, $BC=3$, $CD=6$, $DE=2$, $EA=12$ and $BE=11$. Floyd's algorithm is applied, with the pivots in the order $A$, $B$, $C$, $D$, $E$. In the route table, the entry in row $X$, column $Y$ is the first vertex to travel to when going from $X$ to $Y$; initially it is $Y$ itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).

   (a)

   After iteration 2 (pivot $B$), what is the entry in row $A$, column $C$ of the distance table?

   [1 mark]

   • ANo entry (dash)
   • B$3$
   • C$5$
   • D$8$

   (b)

   After iteration 3 (pivot $C$), what is the entry in row $D$, column $B$ of the route table?

   [1 mark]

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

   (c)

   Complete the algorithm. Find the shortest distance from $E$ to $C$ and give the route.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Four villages $P$, $Q$, $R$ and $S$ are joined by roads with lengths in km: $PQ=3$, $PR=5$, $QR=9$, $QS=7$ and $RS=2$. Floyd's algorithm is applied, with the pivots in the order $P$, $Q$, $R$, $S$. In the route table, the entry in row $X$, column $Y$ is the first vertex to travel to when going from $X$ to $Y$; initially it is $Y$ itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).

   (a)

   Carry out iterations 1 and 2. State each entry of the distance table that changes, with its new value, and the new route table entries.

   [3 marks]

   (b)

   Complete the algorithm. Find the shortest distance and route from $P$ to $S$, and show that the shortest route from $Q$ to $R$ is not the direct road.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A one-way system links four junctions $A$, $B$, $C$ and $D$. The one-way roads and their lengths in km are $A\to B=4$, $A\to C=9$, $B\to C=3$, $B\to D=12$, $C\to D=5$ and $D\to A=2$. Floyd's algorithm is applied, with the pivots in the order $A$, $B$, $C$, $D$. A dash in the distance table means there is no route yet. In the route table, the entry in row $X$, column $Y$ is the first vertex to travel to when going from $X$ to $Y$; initially it is $Y$ itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).

   (a)

   Carry out all four iterations of Floyd's algorithm. For each iteration, state the entries that change, with their new distance and route entry.

   [6 marks]

   (b)

   Use the final tables to find the shortest route from $C$ to $B$ and its length. Evaluate whether Floyd's algorithm is a better choice than Dijkstra's algorithm for a planner who needs the shortest distance between every pair of junctions.

   [6 marks]

   Total for question 4: 12 marks

End of questions