Floyd's algorithmEdexcel A-Level Further Maths: Flashcards

Exam questions on Floyd's algorithm

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).
   Complete the algorithm. Find the shortest distance from $B$ to $D$ and use the final route table to give the route.2 marks
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).
   Complete the algorithm. Find the shortest distance from $E$ to $C$ and give the route.2 marks
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).
   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