3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you initialize ls with 1 on edges ? $\endgroup$ – Tpecatte Sep 16 '13 at 15:08
  • $\begingroup$ @timot, yep, see the ws[i][j] = links.get(i).get(j) and ls[i][j] = 1 lines in the code. $\endgroup$ – Volkan Yazıcı Sep 16 '13 at 15:16
  • $\begingroup$ Have you tried to do the loop in the i,j,k order, instead of your k,i,j order ? Not sure it would change anything but I don't see any other mistake. $\endgroup$ – Tpecatte Sep 17 '13 at 9:53
  • $\begingroup$ @Timot, I changed k-i-j to i-j-k, no changes. It still finds paths with loops. Further, I borrowed the k-i-j order from Cormen's Introduction to Algorithms (2E). $\endgroup$ – Volkan Yazıcı Sep 17 '13 at 10:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you mean replacing ds[i][k] + ds[k][j] with something like Math.max(ds[i][k], ds[k][j]), the algorithm will still generate paths with loop, since a longer path can have an identical maximum edge weight with a smaller one. This also explains why I keep an extra array to store the path lengths as well as path weights. Could you elaborate your answer please? $\endgroup$ – Volkan Yazıcı Sep 16 '13 at 19:06
  • $\begingroup$ Sorry but I am not following you. Your pseudo-code appears exactly the same as original Floyd-Warshall. Would you mind providing at least the pseudo-code for the loop part that I presented at the question? $\endgroup$ – Volkan Yazıcı Sep 17 '13 at 6:49
  • 1
    $\begingroup$ @VolkanYazıcı Sorry for not explicitly adding this. Yes it is like Floyd-W., but with the instruction replaced like in your first comment here, using max. (I did not give that myself at first as we try to avoid doing homework, but is is hard to judge that from a question.) $\endgroup$ – Hendrik Jan Sep 17 '13 at 8:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This example seems impossible. For each i,j,k combination given in your post, we could deduce that, (1) 1-2 < 1-4 && 2-4 < 1-4; (2) 1-3 < 1-2 && 3-2 < 1-2; (3) 3-2 < 3-4 && 2-4 < 3-4; (4) 2-3 < 2-4 && 3-4 < 2-4. While (3) and (4) are contradiction. $\endgroup$ – Mr. Ree May 10 '17 at 8:52
  • $\begingroup$ @Mr.Ree Wow, great job in deducing that. I believe you are correct. I will leave my answer to show that this is NOT what is happening. $\endgroup$ – wookie919 May 10 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.