Floyd's Algorithm (Edexcel A Level Further Maths: Decision Maths 1)

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