Graph algorithms - Minimum cost walk between all pairs of vertices

Find minimum cost walk between all pairs of vertices. Negative cost edges are ok; negative cost cycles are not.

Matrix multiplication

Define w_k,x,y = the cost of minimum cost walk of length at most k from x to y, or ∞ if no such walk exists.

We have a recurrence relation. The base case is:

• w_1,x,x=0;
• w_1,x,y=cost(x,y), if (x,y) is an edge of the graph;
• w_1,x,y=∞, if x≠y and (x,y) is not an edge of the graph;

The actual recurrence is:

• w_k+l,x,y=min(w_k,x,z+w_l,z,y).

The idea is to compute w_k,x,y for a value of k based upon the already computed values for k/2. We need to get to a k greater than n.

The number of operations for computing all w_k,x,y for a given k is O(n³). Doing this up to a k greater than n will take O(n³ log n).

To retrieve the path, we can define a second array, f_k,x,y = the next vertex after x on the walk of cost w_k,x,y. When the minimum in the recurrence is reached for some intermediate vertex z, we set f_2k,x,y = f_k,x,z.

Floyd-Warshall algorithm

It is also based on dynamic programming. We need to have a numbering of all vertices of the graph, X={z₀,z₁,...,z_n-1}.

Then, we define w_k,x,y = the cost of minimum cost walk from x to y, using, as intermediate vertices, only those in the set {z₀,z₁,...,z_k-1}.

The recursion starts like for the matrix multiplication algorithm. Then, we have:

• w_k+1,x,y=min(w_k,x,y, w_k,x,zk+w_k,zk,y).

Finally, w_n,x,y is allowed to use all vertices in the graph.

The algorithm is thus (assuming vertices are the numbers from 0 to n-1):

for i=0 to n-1 do
    for j=0 to n-1 do
        if i==j then
            w[i,j] = 0
        else if (i,j) is edge in G then
            w[i,j] = cost(i,j)
            f[i,j] = j
        else
            w[i,j] = infinity
        endif
    endfor
endfor
for k=0 to n-1 do
    for i=0 to n-1 do
        for j=0 to n-1 do
            if w[i,j] > w[i,k]+w[k,j] then
                w[i,j] = w[i,k]+w[k,j]
                f[i,j] = f[i,k]
            endif
        endfor
    endfor
endfor

The algorithm complexity is O(n³).