algorithm - 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?

标签： algorithmdynamic-programminggraph-theoryshortest-pathfloyd-warshall

Answer 1

考虑所有节点都连接到所有其他节点的图，边的长度为-1。

可以对 k 进行归纳。让我们证明以下表达式：

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

对于k = 0，A[i,j,k] = -1（根据图的定义）。因此，基本条件检查。

现在，A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1]). 使用归纳假设，右边的所有项都是-2 ** (k - 1)。

因此，A[i,j,k] = -2 ** k和abs(A[i,j,n]) = 2 ** n。