Floyd Warshall algorithm

Let’s take the directed graph ABCD , with 4 edges:

An edge AB with a weight of 5 , an edge BC with a weight of 6 , a weight CD with a weight of 3.

The point of this algorithm will be to create as many matrice as there are edges, in order to get the optimal path for each vertex of the graph to another.

As there are 4 nodes, we’ll create 4 matrices. A matrix A1, a matrix A2 , a matrix A3 , and a matrix A4.

First, create a matrix we’ll call A0.

Imagine 4 columns ABCD

A0 :

A 0 5 i i

B i 0 6 0

C i i 0 3

D i i i 0

Then, create the first matrix, the matrix A1. This will be the matrix dedicated to the node A. This node will be the focal point. We’ll refer to it as the point X.

Create a new matrix, but only take the vertical and horizontal values linked with the node A (or X) . Still compute 0 for the paths leading from each node to themselfves Set all the other values as n for null.

A1 :

A 0 5 i i

B i 0 n n

C i n 0 n

D i n n 0

Here is how we are going to proceed .

Currently, the pathes said as “shortest” for each pair , is a path usingthe edge (if it exists) connecting directly the two vertices. All the other ones are set as +infinite.

Here is what we’re going to do for each pair :

For each pair of the graph, there may be a way to start from the same point, and arrive to the same destination, but deciding to go through the point X. We’ll refer to this path as P2.

The current path will be called P1

If there is, we’ll wonder : is the current path shortest than the path P2?

For all the null values , we’ll repeat the same operation.

After finishing the A1 matrice, we’ll then build the second matrice, which will now use the node B as point X . Now, the matrice reference will be the last matrix (the matrix A1).

Do the same operation did in A1. Create a new matrix, taking the horizontal and vertical values of B , and copy it inside the new matrix.

Update the values accordingly.

Then, continue with the same procedure, building the matrice A3,and the matrice A4.

The execution of the function ends where all the matrices were done.

The matrix of reference is the last matrix (in this case, the matrix A4).

Here is the algorithm :

for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if