floyds-algorithm

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