June 5, 2015 - algorithms cpp

# Floyd Warshall Algorithm

Xavier Geerinck

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

- For every row and cell pair:
- Copy over the row and column of the current iteration
- 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 cellfor j=0; j<n; j++ // for every cell part 2 // If current value > new value, replaceif 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:

- | 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 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 cellfor (int j = 0; j < graph.size(); j++) { // for every cell part 2 // If current value > new value, replaceif (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.