# Running Floyd-Warshall algorithm on graph with negative cost cycle

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.

• 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). – G. Bach Oct 6 '13 at 0:35
• 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? – Teresa Oct 6 '13 at 13:38
• 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. – G. Bach Oct 6 '13 at 19:11
• 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. – Teresa Oct 6 '13 at 19:43
• I would like to see that optimization, because that means that optimization made things worse. – G. Bach Oct 6 '13 at 20:58

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.

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