Does rearranging the outerloop in Floyd-Warshall algorithm as most inner loop change the algorithm

Question

The following code is for Floyd-Warshall algorithm

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

I propose to rewrite the code as follows

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

In the new code, I put the original outer loop into the most inner loop. I find that the new code is easy to understand solving all pair shortest path problem. My question is: is the new code equivalent to the original code for Floyd-Warshall algorithm?

Answer 1

No, that will in general not work. At the very heart of the Floyd–Warshall algorithm is the idea to find shortest paths that go via a smaller subset of nodes: 1..k, and to then increase the size of this subset.

It is essential that pairs of nodes will have their distance adapted to the subset 1..k before increasing the size of that subset.

As an example, take the example graph used on Wikipedia:

Let's focus on the path that exists from node 3 to node 1, which has a least-weight path of 2 + -1 + 4 = 5.

Let's run the original algorithm and your variant to see if it identifies this distance:

Original (Correct) Algorithm

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let k = 0; k < n; ++k) {
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // 5 -- correct

Your Suggested Algorithm

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
        for (let k = 0; k < n; ++k) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // Infinity -- wrong

Answer 2

If you turn the outer loop into the inner loop you get matrix multiplication over the tropical semiring (i.e. the one with min as addition and sum as multiplication) instead of Floyd Warshall.

It will compute the lowest-weight path with up to or exactly two steps. You can exponentiate the matrix by repeated squaring to get the same result as Floyd Warshall of course (with complexity O(V^3 log(V)), and it'll handle negative weight cycles better