Floyd's Algorithm (Edexcel A Level Further Maths): Revision Note

Floyd's Algorithm

What is Floyd's Algorithm?

• Floyd's algorithm finds the shortest distance and the shortest route between any pair of nodes in a network

• This is achieved by setting up and updating a pair of matrices

  • The first is a matrix of (least) distances between nodes

    • it is generally called the distance matrix 

    • the final distance matrix shows the shortest distance between any pair of nodes

  • The second matrix allows the shortest route between nodes to be deduced

    • it is generally called the route matrix

• At each stage (iteration) of Floyd's algorithm, both the distance matrix and route matrix are updated

• Floyd's algorithm will seem long winded and slow at first

  • But the symmetry (in undirected networks) in the distance matrix can reduce the amount of work involved whilst also acting as a check

How do I set up the initial distance matrix and initial route matrix for Floyd's algorithm?

• The initial distance matrix has the direct distances between nodes

  • If there is no direct distance the symbol  is used (to represent/assume a very large distance!)

  • In an undirected network, all distance matrices will exhibit symmetry

    • this is because the distance from node A to C, say, will be the same as the distance from C to A

    • this will apply to all pairs of nodes

    • this helps reduce the work required in Floyd's algorithm but also acts as a means of checking each distance matrix 

• The initial route matrix assumes the shortest route between each pair of nodes is a direct link

  • So the shortest route between A and D, say, is to go directly from A to D

  • It doesn't matter if there is no direct link between a pair of nodes

    • this will be accounted for later in Floyd's algorithm

How do I update the distance matrix in Floyd's algorithm?

• For the FIRST iteration highlight the first row and the first column of the distance matrix

  • For the other cells in the distance matrix (except those labelled with a '-')

    • add the corresponding highlighted distances together

    • if this is less than the current distance, then the current distance gets updated

• This process of updating distances is repeated for each iteration of Floyd's algorithm

  • The number of iterations will be equal to the number of nodes

    • On the second iteration, the SECOND row and SECOND column would be highlighted

    • On the iteration, the row and column would be highlighted

How do I update the route matrix in Floyd's algorithm?

• For the FIRST iteration, highlight the first column of the route matrix

• Find the corresponding cells that have been updated in the distance matrix for this iteration

  • These cells are updated with the node in the highlighted column

• This process of updating routes is repeated for each iteration of Floyd's algorithm

  • The number of iterations will be equal to the number of nodes

    • On the second iteration, the SECOND column would be highlighted

    • On the iteration, the column would be highlighted

How do I use Floyd's algorithm to find shortest distances and routes?

• The shortest distance is found by reading off the value from the final distance matrix

• To find the shortest route between nodes, use the final route matrix

  • start on the row for the starting node

  • find the cell that is under the destination node, then move to that row

  • repeat until the cell contains the destination node