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:
- n - 1
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.