4
$\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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you initialize ls with 1 on edges ? $\endgroup$ Commented Sep 16, 2013 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$ Commented Sep 16, 2013 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$ Commented Sep 17, 2013 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$ Commented Sep 17, 2013 at 10:00

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented Sep 16, 2013 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$ Commented Sep 17, 2013 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$ Commented Sep 17, 2013 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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented May 10, 2017 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$ Commented May 10, 2017 at 20:58

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.