Running Floyd-Warshall algorithm on graph with negative cost cycle

ignougroup
Problem Detail: 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.

Asked By : Teresa

Answered By : wookie919

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14839