Floyd's algorithmEdexcel A-Level Further Maths: Revision notes

Floyd's algorithm finds the shortest distance between every pair of vertices in a network at once. It works with two tables, each with a row and a column for every vertex:

• the distance table: the leading diagonal is 0, each other entry is the length of the direct road, or $\infty$ (or a dash) if there is none;
• the route table: the entry in row $X$, column $Y$ is the first vertex to travel to when going from $X$ to $Y$. At the start each entry is just the column vertex $Y$. For an undirected network the distance table is symmetric. For a directed network (one-way roads) it need not be.

There is one iteration for each vertex in turn. Iteration $k$ uses the $k$th vertex as the pivot, so iteration 1 uses the first row and column, iteration 2 the second row and column, and so on. For every pair $X$, $Y$ (neither being the pivot $K$), compare the current distance with going through $K$: $d(X,K)+d(K,Y)<d(X,Y)$ If this is true, replace $d(X,Y)$ by $d(X,K)+d(K,Y)$ and set the route entry $(X,Y)$ equal to the route entry $(X,K)$. Otherwise leave both unchanged. The pivot's own row and column never change during its iteration. An entry of $\infty$ in row $K$ or column $K$ means that pairing cannot improve anything. Use $\infty$ as larger than any number.

Roads $AB=2$, $AC=3$, $BC=7$, $BD=10$, $CD=4$.

• Iteration 1 (pivot $A$): $B\to C$ becomes $2+3=5$ (route entry $A$). Same for $C\to B$. Nothing else.
• Iteration 2 (pivot $B$): $A\to D$ becomes $2+10=12$, route entry $B$ (and $D\to A$ likewise). $A\to C$: $2+5=7>3$, so no change.
• Iteration 3 (pivot $C$): $A\to D$ becomes $3+4=7$ (route entry $C$). $B\to D$ becomes $5+4=9$ (route entry is $(B,C)=A$).
• Iteration 4 (pivot $D$): no entry improves. Final distances: $AB=2$, $AC=3$, $AD=7$, $BC=5$, $BD=9$, $CD=4$.

The distance table gives the length. To find the route from $X$ to $Y$, look up $(X,Y)$ in the route table to get the next vertex $Z$. Then look up $(Z,Y)$, and continue until you reach $Y$. From the worked example: $B\to D$: $(B,D)=A$, $(A,D)=C$, $(C,D)=D$. The route is $B-A-C-D$ with length $2+3+4=9$. Always check by adding the road lengths along the route; the total must equal the table entry.

• One run gives the shortest distance between every pair. Dijkstra's algorithm gives them only from one start vertex, so it would need to be run from each vertex in turn.
• If only one start vertex is needed, Dijkstra's is quicker, as Floyd's does $n$ iterations on an $n\times n$ table.
• A network with $n$ vertices needs exactly $n$ iterations.
• For a directed network, treat $d(X,Y)$ and $d(Y,X)$ separately, and only update using arcs that exist.
• Show each iteration clearly, with the changed entries, to earn the method marks.