Floyd Warshall Algorithm

Floyd Warshall Algorithm

Introduction

The Floyd-Warshall algorithm is an algorithm used for finding the shortest paths in a weighted graph (just as Prim's Algorithm is one).

The algorithm works by starting from a graph matrix (n x m size) and then iterating for every row and column pair in this graph. For every iteration we will copy over the values from the current row and column pair. As a last step we now have to check every unfilled cell for some conditions:

  • Is it in a infinite row or column (from the copied row and column pair)? --> Yes? then copy the old value
  • Else compute the sum of the row and column headings.
  • If the computed sum is smaller than the previous value, replace it.

Pseudocode

In pseudocode this becomes:

  1. For every row and cell pair:
  2. Copy over the row and column of the current iteration
  3. For every cell check the following:
  • If current row or column iteration is infinity, copy the value (expect if it the cell is a negative value!)
  • Else compute sum of row and column iteration value, if < old value replace old value.

Let's formulate this as a pseudocode that lies close to the coding languages:

for k=0; k<n; k++ // For every iteration (an iteration is a row/col pair)
  for i=0; i<n; i++ // For every cell
    for j=0; j<n; j++ // for every cell part 2 // If current value > new value, replace
      if graph[i][j] > graph[i][k] + graph[k][j]
        graph[i][j] = graph[i][k] + graph[k][j]
      end if

Example

Let's explain this with an example. Let's say we have the following graph:

Floyd-Warshall

When we now compute the graph it's matrix we get this table:

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|8|∞|1| |2|∞|0|1|∞| |3|4|∞|0|∞| |4|∞|2|9|0|

Now we start iterating as explained above. (The italic numbers are the values that were copied over).

Iteration: 1 Here we just have to compute the values in the cells: (2, 3) and (4, 3)

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|8||1| |2||0|1|∞| |3|4|12|0|5| |4||2|9|0|

Iteration: 2

Here we computer the cells in the column 3 (expect the copied over cell of course). These became 9, 0 (same as before, smallest number that we have) and 3 (3 < 9)

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|8|9|1| |2||0|1|| |3|4|12|0|5| |4|∞|2|3|0|

Iteration: 3

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|8|9|1| |2|5|0|1|6| |3|4|12|0|5| |4|7|2|3|0|

Iteration: 4

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|3|4|1| |2|5|0|1|6| |3|4|7|0|5| |4|7|2|3|0|

Coding this in C++

Coding this is pretty straightforward, we can follow our pseudocode exactly as it is written. When we code this we get something like this:

#include
#include
#include

#define INF 100000

void floyd_ws_algorithm(std::vector< std::vector > &graph);

int main(int argc, const char * argv[]) {
  std::vector< std::vector > graph;

  graph = {
    { 0, 8, INF, 1 },
    { INF, 0, 1, INF },
    { 4, INF, 0, INF },
    { INF, 2, 9, 0 },
  };

  floyd_ws_algorithm(graph);

  for (int i = 0; i < graph.size(); i++) {
    for (int j = 0; j < graph.size(); j++) {
      std::cout << graph[i][j] << " ";
    }

    std::cout << std::endl;
  }

  std::cout << std::endl;

  return 0;
}

// Execute prim's algorithm for the given start node, note this is the index of the graph
void floyd_ws_algorithm(std::vector< std::vector > &graph) {
  for (int k = 0; k < graph.size(); k++) { // For every iteration (an iteration is a row/col pair)
    for (int i = 0; i < graph.size(); i++) { // For every cell
      for (int j = 0; j < graph.size(); j++) { // for every cell part 2 // If current value > new value, replace
        if (graph[i][j] > graph[i][k] + graph[k][j]) {
          graph[i][j] = graph[i][k] + graph[k][j];
        }
      }
    }
  }
}

When we check this we also get the solution:

|-|1|2|3|4| |:-:|:-:|:-:|:-:|:-:| |1|0|3|4|1| |2|5|0|1|6| |3|4|7|0|5| |4|7|2|3|0|

which is the same solution as when we did this manually.

Subscribe to Xavier Geerinck

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe