6
$\begingroup$

I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, or 1. Suppose that G is strongly connected, with at least one u-v path for every pair u,v of vertices, and that G may have a negative-cost cycle. How large can the final entries A[i,j,n] be, in absolute value (n denotes number of vertices). Choose the smallest number that is guaranteed to be a valid upper bound? There is the following answers:

  1. +∞
  2. n^2
  3. n - 1
  4. 2^n

I have ruled out 3. (n-1) and 1. (+∞) since if a graph has a negative cost cycle, the absolute final value of a path including a negative cycle can be increased further than n-1. The answer also cannot be +∞ since the algorithm stops after a finite number of steps. But I am having trouble between answers 2. and 4. I am more inclined to 4. since I have run some test cases, and final values seemed to comply to an exponential growth. But I cannot find a proof for it.

$\endgroup$
  • 1
    $\begingroup$ If you have a graph with $n$ nodes and you know there is a path between each pair of nodes, what is the maximum length of such a path, counting in edges instead of edge weights? And a note on your thoughts about why it can't be $n-1$: if it can be shorter than that, then it certainly can be shorter than $n^2$ and $2^n$. This question isn't about finding the longest path you can build, but about finding the greatest possible length of a shortest path (since Floyd-Warshall looks for shortest paths). $\endgroup$ – G. Bach Oct 6 '13 at 0:35
  • $\begingroup$ When a graph has a negative cost cycle, Floyd-Warshall may not give the right answers. If there were no negative cost cycle, the answer would be n-1. However because there can be one, the greatest absolute final value would be greater than n-1. In fact, running Floyd-Warshall on a graph G (V,E,C) = (5 vertices, 10 edges, -1 edge cost for all edges) Edges: (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (3, 1), (2, 5), (4, 2), (5, 3), (1, 4) the largest absolute final value is 98. The answers n^2 or 2^n are not valid upper bounds for this graph either. Could someone guide me here? $\endgroup$ – Teresa Oct 6 '13 at 13:38
  • $\begingroup$ Oksana, the correct answer is $n-1$. For some reason you get mixed up with the negative cost cycles; all they can do to the distances calculated by Floyd-Warshall is make them cheaper, not more expensive. I don't understand how you arrive at 98 for that graph, all distances have to be negative if there are only negative-weight edges. $\endgroup$ – G. Bach Oct 6 '13 at 19:11
  • $\begingroup$ I was using an optimization of Floyd-Warshall. This is where I went wrong. But once I implemented the basic algorithm, I got -20. I tried a few more test cases, and they led me to the correct answer. $\endgroup$ – Teresa Oct 6 '13 at 19:43
  • $\begingroup$ I would like to see that optimization, because that means that optimization made things worse. $\endgroup$ – G. Bach Oct 6 '13 at 20:58
4
$\begingroup$

I think the answer is 4, and here is why.

Assume the graph is fully connected with all edges having weight of -1.

Now let's consider the three loops of Floyd-Warshall algorithm:

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:

Since -2 is "shorter" than -1, after we finish k = 1, the weight for i -> k = 1 -> j is -2 for most i and j (exceptions would be i = k and j = k).

After we finish k = 2, the weight for i -> k = 2 -> j is -4 for most i and j. This is because i -> 1 -> 2 -> 1 -> j is the shortest, giving us -4.

And so on and so on for the exponential growth.

Floyd-Warshall algorithm does not guarantee that we will find a simple shortest path, that is, a path containing only one instance of each vertex.

$\endgroup$
  • $\begingroup$ Negative values are smaller than $0$, which is smaller than $2^n$ for any number of nodes $n$. $\endgroup$ – G. Bach Oct 6 '13 at 20:57
  • $\begingroup$ The question says "in absolute value". $\endgroup$ – wookie919 Oct 6 '13 at 21:49
  • $\begingroup$ Oh, I must have read over that part - you are right then, of course. $\endgroup$ – G. Bach Oct 6 '13 at 23:48
  • $\begingroup$ Why when k = 2 the shortest path is -4 and not -3? $\endgroup$ – spkenny Dec 2 '16 at 8:30

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.