Floyd-Warshall algorithm on a directed graph in which every edge's length is either -1, 0, or 1

Question

I'm taking the Algorithms: Design and Analysis II course, and one of the questions is as follows:

Suppose we run the Floyd-Warshall algorithm on a directed graph G = (V,E) in which every edge's length is either -1, 0, or 1. Suppose further that G is strongly connected, with at least one u-v path for every pair u,v of vertices. The graph G may or may not have a negative-cost cycle. How large can the final entries A[i,j,n] be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual, n denotes |V|.) [WARNING: for this question, make sure you refer to the implementation of the Floyd-Warshall algorithm given in lecture, rather than to some alternative source.]

• 2^n
• n -1
• n^2
• infinity

The lecture video that's been referred to is on YouTube. For reference, the algorithm is as follows:

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      A[i,j,k] = min {A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1]}

The correct answer is the first one, 2^n, and the hint says it can be proved by induction. I can't seem to wrap my head around it. Can someone help me understand?

Answer 1

Consider the graph where all nodes are connected to all other nodes with an edge of length -1.

The induction can be done on k. Let's prove the following expression:

A[i,j,k] = -2 ** k

For k = 0, A[i,j,k] = -1 (by definition of graph). So, the base condition checks out.

Now, A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1]). Using the inductive hypothesis, all the terms on the right will be -2 ** (k - 1).

Hence, A[i,j,k] = -2 ** k and abs(A[i,j,n]) = 2 ** n.