# Xavier Geerinck

My thoughts, tutorials and learnings

June 5, 2015 - algorithms cpp

# Floyd Warshall Algorithm

Xavier Geerinck

@XavierGeerinck

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

## 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:

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

-1234
1081
201
340
4290

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)

-1234
1081
201
341205
4290

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)

-1234
10891
201
341205
4230

Iteration: 3

-1234
10891
25016
341205
47230

Iteration: 4

-1234
10341
25016
34705
47230

## 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 100000void 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 graphvoid 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:

-1234
10341
25016
34705
47230

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

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

Xavier Geerinck © 2020