# Floyd-Warshall algorithm

Sep 4, 2017

## The story behind this post

Recently I’ve received `+10` karma on StackOverflow. I was curious for what question or answer and clicked to check this. It appeared to be a seven-year-old answer about a Floyd-Warshall algorithm. I was surprised with both my bad English (back those days…) and the very small value the answer had. So I’ve revised it and here it is – the brand-new version!

## The definitions

Let us have a graph, described by matrix `D`, where `D[i][j]` is the length of the edge `(i -> j)` (from graph’s vertex with index `i` to the vertex with index `j`).

Matrix `D` has the size of `N * N`, where `N` is a total number of vertices in a graph because we can reach the maximum of paths by connecting each graph’s vertex to each other.

Also, we’ll need matrix `R`, where we will store the vertices of the shortest paths (`R[i][j]` contains the index of a vertex, where the shortest path from vertex `i` to vertex `j` lies).

Matrix `R` has the same size as `D`.

The Floyd-Warshall algorithm performs these steps:

1. initialize the matrix of all the paths between any two pairs of vertices in a graph with the edge’s end vertex (this is important since this value will be used for path reconstruction)

2. for each pair of connected vertices (read: for each edge `(u -> v)`), `u` and `v`, find the vertex, which forms shortest path between them: if the vertex `k` defines two valid edges `(u -> k)` and `(k -> v)` (if they are present in the graph), which are together shorter than path `(u -> v)`, then assume the shortest path between `u` and `v` lies through `k`; set the shortest pivot point in matrix `R` for edge `(u -> v)` to be the corresponding pivot point for edge `(u -> k)`

But how do we read the matrix `D`?

## Inputs

Take sample graph:

In GraphViz it would be described as follows:

``````digraph G {
layout = "circo";

0->2 [label = "1"];
2->3 [label = "5"];
3->1 [label = "2"];
1->2 [label = "6"];
1->0 [label = "7"];
}
``````

We first create a two-dimensional array of size `4` (since there are exactly `4` vertices in our graph).

We initialize its main diagonal (the items, whose indices are equal, for ex. `G[0, 0]`, `G[1, 1]`, etc.) with zeros, because the shortest path from vertex to itself has the length `0` and the other elements with a very large number (to indicate there is no edge or an infinitely long edge between them). The defined elements, corresponding to graph’s edges, we fill with edges’ lengths:

``````int N = 4;
int[,] D = new int[N, N];

for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}
``````

And let’s say we initialize our `D` matrix by hand:

``````D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;
``````

## The algorithm itself

Now that we are on a same page with definitions, algorithm can be implemented like this:

``````int[,] R = new int[N, N];

// Initialise the routes matrix R, essentially saying "the shortest path from u to v is straight"
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
R[i, t] = t;
}
}

// Floyd-Warshall algorithm; note the order of iterators DOES matter:
for (int k = 0; k < N; k++) {
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
// check if the shortest path from "u" to "v" is actually through "k"
if (D[u, v] > D[u, k] + D[k, v]) {
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}
``````

Let’s “animate” this algorithm in few steps for the sample graph from above:

### Initial state

• the `D` matrix contains distance from vertex `u` to vertex `v`, where both `u` and `v` are indexes of those vertices in a graph and `u` is the index of a row and `v` is the index of the column in any of the matrices `R` and `D`
• path from `u` to `u` is thought to be infinitely long meaning we do not allow this type of paths
• in matrix `R` we define the shortest path from `u` to `v` to lie through `v`
 D 0 1 2 3 0 0 ∞ 1 ∞ 1 7 0 6 ∞ 2 ∞ ∞ 0 5 3 ∞ 2 ∞ 0
 R 0 1 2 3 0 0 1 2 3 1 0 1 2 3 2 0 1 2 3 3 0 1 2 3

### Step 1

We try to find the vertex which makes the shorter path through itself than the direct path between two vertices. E.g. for every vertex `k` we find the pair of vertices `u` and `v` where path `u -> v` is longer than the path `u -> k -> v`. If we found one - we will update the matrices `D` and `R`, correspondingly.

For vertex `k = 0` we will check each combination of:

paths through `0` starting at `0`:

• `0 -> 0` vs `0 -> 0 -> 0`
• `0 -> 1` vs `0 -> 0 -> 1`
• `0 -> 2` vs `0 -> 0 -> 2`
• `0 -> 3` vs `0 -> 0 -> 3`

paths through `0` starting at `1`:

• `1 -> 0` vs `1 -> 0 -> 0`
• `1 -> 1` vs `1 -> 0 -> 1`
• `1 -> 2` vs `1 -> 0 -> 2`
• `1 -> 3` vs `1 -> 0 -> 3`

paths through `0` starting at `2`:

• `2 -> 0` vs `2 -> 0 -> 0`
• `2 -> 1` vs `2 -> 0 -> 1`
• `2 -> 2` vs `2 -> 0 -> 2`
• `2 -> 3` vs `2 -> 0 -> 3`

paths through `0` starting at `3`:

• `3 -> 0` vs `3 -> 0 -> 0`
• `3 -> 1` vs `3 -> 0 -> 1`
• `3 -> 2` vs `3 -> 0 -> 2`
• `3 -> 3` vs `3 -> 0 -> 3`

As you can see, there are lots of invalid paths here - those which either do not exist or do not make sense. Examples are: paths which do not exist (like `0 -> 3`) and paths to any vertex through source vertex (like `0 -> 0 -> 0` and `0 -> 0 -> (any)`).

We could easily reduce the amount of the steps performed by the algorithm by throwing few `if` conditions to check for those cases.

But let’s first finish animating this step: there are very few valid paths amongst `N * N === 16` of those we’ve checked. And only one comparison: for path `1 -> 2` vs `1 -> 0 -> 2` we compare `6` (direct) and `7 + 1 = 8` (`1 -> 0` and then `0 -> 2`).

So there are no changes in our matrices.

 D 0 1 2 3 0 0 ∞ 1 ∞ 1 7 0 6 ∞ 2 ∞ ∞ 0 5 3 ∞ 2 ∞ 0
 R 0 1 2 3 0 0 1 2 3 1 0 1 2 3 2 0 1 2 3 3 0 1 2 3

### Step 2

For vertex `1` we will check each combination of:

paths through `1` starting at `0`:

• `0 -> 0` vs `0 -> 1 -> 0`
• `0 -> 1` vs `0 -> 1 -> 1`
• `0 -> 2` vs `0 -> 1 -> 2`
• `0 -> 3` vs `0 -> 1 -> 3`

paths through `1` starting at `1`:

• `1 -> 0` vs `1 -> 1 -> 0`
• `1 -> 1` vs `1 -> 1 -> 1`
• `1 -> 2` vs `1 -> 1 -> 2`
• `1 -> 3` vs `1 -> 1 -> 3`

paths through `1` starting at `2`:

• `2 -> 0` vs `2 -> 1 -> 0`
• `2 -> 1` vs `2 -> 1 -> 1`
• `2 -> 2` vs `2 -> 1 -> 2`
• `2 -> 3` vs `2 -> 1 -> 3`

paths through `1` starting at `3`:

• `3 -> 0` vs `3 -> 1 -> 0`
• `3 -> 1` vs `3 -> 1 -> 1`
• `3 -> 2` vs `3 -> 1 -> 2`
• `3 -> 3` vs `3 -> 1 -> 3`

This case is more interesting - there are more things to compare. Let’s see each combination:

1. `3 -> 0` does not exist (`inf`)
2. `3 -> 1` has length `2` and `1 -> 0` has length `7`, the indirect path `3 -> 1 -> 0` has length `9`

Hence we will update matrices `D` and `R` reflecting that.

For path `3 -> 1 -> 2`:

1. there is no path from `3` to `2` directly, so its length is `inf`
2. `3 -> 1` has length `2` and `1 -> 2` has length `6`, the total is `8` which is infinitely better than infinity

Here are the updated matrices:

 D 0 1 2 3 0 0 ∞ 1 ∞ 1 7 0 6 ∞ 2 ∞ ∞ 0 5 3 9 2 8 0
 R 0 1 2 3 0 0 1 2 3 1 0 1 2 3 2 0 1 2 3 3 1 1 1 3

### Step 3

For vertex `2` we will check each combination of:

paths through `2` starting at `0`:

• `0 -> 0` vs `0 -> 2 -> 0`
• `0 -> 1` vs `0 -> 2 -> 1`
• `0 -> 2` vs `0 -> 2 -> 2`
• `0 -> 3` vs `0 -> 2 -> 3`

paths through `2` starting at `1`:

• `1 -> 0` vs `1 -> 2 -> 0`
• `1 -> 1` vs `1 -> 2 -> 1`
• `1 -> 2` vs `1 -> 2 -> 2`
• `1 -> 3` vs `1 -> 2 -> 3`

paths through `2` starting at `2`:

• `2 -> 0` vs `2 -> 2 -> 0`
• `2 -> 1` vs `2 -> 2 -> 1`
• `2 -> 2` vs `2 -> 2 -> 2`
• `2 -> 3` vs `2 -> 2 -> 3`

paths through `2` starting at `3`:

• `3 -> 0` vs `3 -> 2 -> 0`
• `3 -> 1` vs `3 -> 2 -> 1`
• `3 -> 2` vs `3 -> 2 -> 2`
• `3 -> 3` vs `3 -> 2 -> 3`

The valid comparisons are:

• `0 -> 3` vs `0 -> 2 -> 3`
• `1 -> 3` vs `1 -> 2 -> 3`

In first case, we compare infinity (`0 -> 3`) to `1 + 5 == 6` (`0 -> 2` and then `2 -> 3`). In second case we compare infinity again (`1 -> 3`) to `6 + 5 == 11` (`1 -> 2` and then `2 -> 3`). In both cases we select the path through vertex `2`.

 D 0 1 2 3 0 0 ∞ 1 6 1 7 0 6 11 2 ∞ ∞ 0 5 3 9 2 8 0
 R 0 1 2 3 0 0 1 2 2 1 0 1 2 2 2 0 1 2 3 3 1 1 1 3

### Step 4

For vertex `3` we will check each combination of:

paths through `3` starting at `0`:

• `0 -> 0` vs `0 -> 3 -> 0`
• `0 -> 1` vs `0 -> 3 -> 1`
• `0 -> 2` vs `0 -> 3 -> 2`
• `0 -> 3` vs `0 -> 3 -> 3`

paths through `3` starting at `1`:

• `1 -> 0` vs `1 -> 3 -> 0`
• `1 -> 1` vs `1 -> 3 -> 1`
• `1 -> 2` vs `1 -> 3 -> 2`
• `1 -> 3` vs `1 -> 3 -> 3`

paths through `3` starting at `2`:

• `2 -> 0` vs `2 -> 3 -> 0`
• `2 -> 1` vs `2 -> 3 -> 1`
• `2 -> 2` vs `2 -> 3 -> 2`
• `2 -> 3` vs `2 -> 3 -> 3`

paths through `3` starting at `3`:

• `3 -> 0` vs `3 -> 3 -> 0`
• `3 -> 1` vs `3 -> 3 -> 1`
• `3 -> 2` vs `3 -> 3 -> 2`
• `3 -> 3` vs `3 -> 3 -> 3`

This case is the last one. It is similar to the previous two. But please note that we are using the matrix values from the previous step.

For path `0 -> 1`:

1. direct path from `0` to `1` does not exist, take it as `inf`
2. shortest path from `0` to `3` (whichever it is) has length `6`; `3 -> 1` has length `2`; the total path has length `8` which is better than infinity

For path `2 -> 0`:

1. direct path `2 -> 0` does not exist
2. the edge `2 -> 3` exists and has length `5`; path from `3` to `0` has length `9`; so the shortest path from `2` to `0` through `3` will have length `9 + 5 == 14`

For path `2 -> 1`:

1. there is no direct path `2 -> 1`
2. the path `2 -> 3` is `5` and `3 -> 1` is `2`, so `2 -> 3 -> 1` is `7`

Both matrices `R` and `D` will be updated to reflect that:

 D 0 1 2 3 0 0 8 1 6 1 7 0 6 11 2 14 7 0 5 3 9 2 8 0
 R 0 1 2 3 0 0 2 2 2 1 0 1 2 2 2 3 3 2 3 3 1 1 1 3

And then the algorithm is done.

## Path reconstruction

In order to reconstruct the path from vertex `u` to vertex `v`, you need follow the elements of matrix `R`, effectively going “through” each vertex:

``````    List<Int32> Path = new List<Int32>();

while (start != end) {

start = R[start, end];
}

``````

Let’s follow this logic in steps again, “animating” the algorithm. For instance, the longest path in this graph possible, from `0` to `1`:

1. `start = 0, end = 1`
2. `R[0, 1] == 2, start = 2, end = 1`
3. `R[2, 1] == 3, start = 3, end = 1`
4. `R[3, 1] == 1, start = 1, end = 1`

So the path from `0` to `1` is all the values the `start` variable takes (except last), namely: `0 -> 2 -> 3`.

## Summary

The whole code could be wrapped in a couple of methods:

``````using System;
using System.Collections.Generic;

public class FloydWarshallPathFinder {
private int N;
private int[,] D;
private int[,] R;

public FloydWarshallPathFinder(int NumberOfVertices, int[,] EdgesLengths) {
N = NumberOfVertices;
D = EdgesLengths;
R = null;
}

public int[,] FindAllPaths() {
R = new int[N, N];

for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
R[i, t] = t;
}
}

for (int k = 0; k < N; k++) {
for (int v = 0; v < N; v++) {
for (int u = 0; u < N; u++) {
if (D[u, k] + D[k, v] < D[u, v]) {
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}

return R;
}

public List<Int32> FindShortestPath(int start, int end) {
if (R == null) {
FindAllPaths();
}

List<Int32> Path = new List<Int32>();

while (start != end) {

start = R[start, end];
}

return Path;
}
}

public class MainClass {
public static void Main() {
int N = 4;
int[,] D = new int[N, N];

for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}

D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;

FloydWarshallPathFinder pathFinder = new FloydWarshallPathFinder(N, D);

int start = 0;
int end = 1;

Console.WriteLine("Path: {0}", String.Join(" -> ", pathFinder.FindShortestPath(start, end).ToArray()));
}
}
``````

You can read ‘bout this algorithm on wikipedia and get some data structures generated automatically here