10.4.2 Floyd's Algorithm

Floyd's algorithm, also known as the Floyd-Warshall algorithm, is a method for finding the shortest paths between all pairs of nodes in a weighted graph. It is particularly effective for dense graphs and works for both directed and undirected graphs, provided there are no negative weight cycles.

How Floyd's Algorithm Works

Key Concepts

The algorithm iteratively improves estimates of the shortest paths by considering each node as an intermediate step.
It updates a distance matrix and (optionally) a route matrix to track the shortest distances and routes between pairs of nodes.

Step-by-Step Process

Initialisation:

Start with the adjacency matrix of the graph. If there is no direct connection between two nodes, the distance is set to ∞ (infinity), except for the diagonal entries (distance from a node to itself), which are 0.
Optionally, initialise a route matrix where the entry $R[i][j]R[i][j]$ stores the node used to travel directly from $i$ to $j$

Iterative Updates:

Use each node $k$ (in turn) as an intermediate node to check if it provides a shorter path between any two other nodes $i$ and $j$ .
Update the distance matrix using the formula:

d[i][j] = \min(d[i][j], d[i][k] + d[k][j])

Update the route matrix to reflect the intermediate node $k$ if the shorter path is found.

Repeat for All Nodes:

Perform these updates iteratively for $k=1$ to $n$ , where $n$ is the number of nodes in the graph.

Termination:

The algorithm completes when all possible intermediate nodes have been considered.

Worked Example

infoNote

Problem

Find the shortest paths between all pairs of nodes in the graph below:

Node Pair	Weight
A → B	3
A → C	∞
A → D	7
B → A	8
B → C	2
B → D	∞
C → A	5
C → B	∞
C → D	1
D → A	2
D → B	∞
D → C	∞

Initialisation Create the initial distance matrix $D_0$ and route matrix $R_0$ :

Distance Matrix $D_0$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 3 & ∞ & 7 \\ B & 8 & 0 & 2 & ∞ \\ C & 5 & ∞ & 0 & 1 \\ D & 2 & ∞ & ∞ & 0 \\ \end{array}

Route Matrix $R_0$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & B & - & D \\ B & A & - & C & - \\ C & A & - & - & D \\ D & A & - & - & - \\ \end{array}

First Iteration ( $k = A$ ) Use $A$ as the intermediate node to update distances:

d[i][j] = \min(d[i][j], d[i][A] + d[A][j])

Updated Distance Matrix $D_1$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 3 & ∞ & 7 \\ B & 8 & 0 & 2 & 15 \\ C & 5 & 8 & 0 & 1 \\ D & 2 & 5 & ∞ & 0 \\ \end{array}

Updated Route Matrix $R_1$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & B & - & D \\ B & A & - & C & A \\ C & A & A & - & D \\ D & A & B & - & - \\ \end{array}

Second Iteration ( $k = B$ ) Use $B$ as the intermediate node to update distances:

Updated Distance Matrix $D_2$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 3 & 5 & 7 \\ B & 8 & 0 & 2 & 15 \\ C & 5 & 8 & 0 & 1 \\ D & 2 & 5 & 7 & 0 \\ \end{array}

Updated Route Matrix $R_2$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & B & B & D \\ B & A & - & C & A \\ C & A & A & - & D \\ D & A & B & B & - \\ \end{array}

Third Iteration ( $k = C$ )

Repeat using $C$ as the intermediate node.

Fourth Iteration ( $k = D$ )

Finally, use $D$ as the intermediate node.

Final Result

After all iterations, the final distance matrix and route matrix give the shortest paths between all pairs of nodes.

Note Summary

infoNote

Common Mistakes

Incorrect Initialisation Forgetting to set $d[i][i] = 0$ and all non-edges to ∞.
Order of Iterations Not completing the updates row by row as required.
Missing Updates Failing to check all pairs $i, j$ when using $k$ as the intermediate node.
Route Matrix Errors Forgetting to update the route matrix when a shorter path is found.
Negative Cycles Using the algorithm on graphs with negative weight cycles, which causes incorrect results.

infoNote

Key Formulas/Theorems

Distance Update Rule

d[i][j] = \min(d[i][j], d[i][k] + d[k][j])

Route Matrix Update If a shorter path is found, update $R[i][j]$ to reflect the intermediate node $k$ .
Termination Criterion The algorithm completes after $n$ iterations, where $n$ is the number of nodes.

Floyd's Algorithm Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1

10.4.2 Floyd's Algorithm

How Floyd's Algorithm Works

Key Concepts

Step-by-Step Process

Worked Example

Problem

Note Summary

Common Mistakes

Key Formulas/Theorems

500K+ Students Use These Powerful Tools to Master Floyd's Algorithm For their A-Level Exams.

Other Revision Notes related to Floyd's Algorithm you should explore