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:

Floyd-Warshall

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

-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

Twitter - LinkedIn