# 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 both of 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 shortest paths (`R[i][j]` contains the index of a next vertex in the shortest path, starting at vertex `i` and ending at vertex `j`).

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

Let us have a graph:

In GraphViz it would be described as follows: ```dot digraph G { 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;
}
}
}

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:

``````// Initialise the routes matrix R
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
R[i][t] = t;
}
}

// Floyd-Warshall algorithm:
for (int k = 0; k < N; k++) {
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
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];
}
}
}
}
``````

After the algorithm run, the matrix `R` will be filled with vertices’ indices, describing shortest paths between them.

## Path reconstruction

In order to reconstruct the path from vertex `u` to vertex `v`, you need follow the elements of matrix `R`:

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

while (start != end)
{
Path.Add(start);

start = R[start, end];
}

Path.Add(end);
``````

## 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)
{
Path.Add(start);

start = R[start, end];
}

Path.Add(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