Floyd-Warshall in a Nutshell

This is article is intended to explain Floyd-Warshall algorithm (shortest distance finding algorithm), especially for those who new with this.

Floyd-Warshall Algorithm

As described by wikipedia, it is "a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights". Simply said, it is an algorithm which you can find the shortest path for all possible routes, given several possible routes with different "costs" between each route. As simple as it is.

Example

Say that we have 5 routes (1,2,3,4 and 5) like this:

1---2

|  / \

| /   5

|/   /

3---4

With the path cost as described like this (if you have difficulty in measure, just use meters or kilometers as substitution):

1 --> 2 = 2

1 --> 3 = 3

2 --> 5 = 1

2 --> 3 = 7

3 --> 4 = 3

4 --> 5 = 2

And we need the shortest route from 5 to 3. Using normal brain, we will use this sort of algorithm:

1. Pick point 5
2. Pick all possible routes, in this case:
   (1) 5-2-1-3 (the sum is 1 + 2 + 3 or 6)
   (2) 5-2-3 (the sum is 1+7 or 8)
   (3) 5-4-3 (the sum is 2 + 3 or 5)
3. Pick the lowest cost, which is route 5-4-3, with cost of 5

That's it for the single-point destination calculation.

Using Floyd-Warshall Algorithm

Using Floyd-Warshall Algorithm, you can find all shortest path from the possible routes. There are some steps to do it.

Represent the paths into 2-dimensional arrays

The path from example above need to be represented using two dimensional arrays. For example, say that we want to map route no.2 into arrays, it will be represented like this:

{ 2, 0, 7, iNf, 1}

The first value (2), represent the route between point 2 and point 1. In array, it is represented as path[2][1]. The second value (0) it represent the route from point 2 to point 2, which is zero or no distance. The fourth one, iNf or infinite, represent the route from point 2 to point 4, in which cannot be achievable, and causing it to become infinite or not possible. In programming language, the infinite can be replaced by maximum number of int.

In short, we can represent the two dimensional array as this:

         from

       1 2 3 4 5

     ------------

   1 | 0 2 3 i i

   2 | 2 0 7 i 1

to 3 | 3 7 0 3 i

   4 | i i 3 0 2

   5 | i i i 2 0

(the i symbol represent infinite)

The pseudocode

The sinppet below is a pseudocode for Floyd-Warshall algorithm based on the case above.

for k from 1 to 5
   for i from 1 to 5
      for j from 1 to 5
         if dist[i][j] > dist[i][k] + dist[k][j] then

            dist[i][j] = dist[i][k] + dist[k][j]

This nested loop will iterate through each route / path, and compare with another path having the same point. It will see whether the other path has shorter cost than the initial, if it is shorter, then it will be swapped.

Say that now we have iteration of:
k = 3
i = 4
j = 1

Then the array can be replaced with: if dist[4][1] > dist[4][3] + dist[3][1]. Or the same as if iNf > 3 + 3. The comparison is true, meaning that the dist[4][1] will be replaced by 6, or the same as the cost of route 1-4-3. After running the logic, this is the expected result:

           from

       1  2  3  4  5

     ---------------

   1 | 0  2  3  6  8

   2 | 2  0  5  8  10

to 3 | 3  5  0  3  5

   4 | 6  8  3  0  2

   5 | 8 10  5  2  0

When comparing the result in this case, the shortest cost in route 5 to 3 is valued 5, which is fit with out first try.