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