Shortest Minimax Path via Floyd-Warshall

Question

I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.)

Floyd-Warshall algorithm contains the following loop to enhance the distance (ds) and the next vertex (ns) matrices at each iteration.

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ds[i][k] != inf && ds[k][j] != inf) {
                final int d = ds[i][k] + ds[k][j];
                if (d < ds[i][j]) {
                    ds[i][j] = d;
                    ns[i][j] = k;
                }
            }

I replaced ds with two new matrices: ws (weights) and ls (lengths). Further, updated the iteration step as follows:

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ws[i][k] != inf && ws[k][j] != inf) {
                final int w = Math.max(ws[i][k], ws[k][j]);
                final int l = ls[i][k] + ls[k][j];
                if (w < ws[i][j] || (w == ws[i][j] && l < ls[i][j])) {
                    ws[i][j] = w;
                    ls[i][j] = l;
                    ns[i][j] = k;
                }
            }

However, the modified algorithm finds paths with loops, that is, paths such as 1-3-2-3-4. While the maximum edge weight of the paths 1-3-2-3-4 and 1-3-4 are identical, the latter has a shorter path length and supposed to be returned by the enhanced Floyd-Warshall. Any ideas?

A working Java version of both algorithms and a test case which produces a path with loop can be found here.

Edit: Since no solutions were presented yet, I implemented my own shortest minimax path algorithm using incremental link removal method. Java sources to the solutions can be accessed from the above link.

Answer 1

No need to introduce two arrays. In the original algorithm the distance equals the minimum (over all paths) of the sum of edges (in the path). The new variant defines a distance as the minimum (over all paths) of the maximum of edges (in the path).

Then one only needs to rethink the instruction

       final int d = ds[i][k] + ds[k][j];

In my understanding of Floyd-Warshall the array ns stores the highest number of the shortest path: it is updated to k each time a shorter path is found. To retrieve the path itself I would use a recursive procedure short[i,j] = short[i,k] + short[k,j] where k=ns[i,j] and provided k<>i and k<>j. (adapted to your programming syntax)

In that way no vertex will be repeated on a shortest path, but that part of Foyd-Warshall I always find hard to explain.

Answer 2

I deleted my previous answer because it was incorrect. Maybe the following is what is happening.

When the nested for loops reach:

i = 1, j = 4, k = 2

Let's suppose 1-2-4 is better than 1-4. Then we reach:

i = 1, j = 2, k = 3

Let's suppose 1-3-2 is better than 1-2. Then the current best path from 1 to 4 becomes 1-3-2-4. Then we reach:

i = 1, j = 4, k = 3

If 1-3-2-4 is better than 1-3-4 no change will occur.

Then we reach:

i = 2, j = 4, k = 3

If 2-3-4 is better than 2-4, the problem that you are seeing will occur. Because now the best path from 1 to 4 is 1-3-2-3-4.

---

EDIT: The above example has been shown to be impossible (in the comments). Leaving the answer rather than deleting it to prevent others from making the same mistake.