有向图上的 Floyd-Warshall 算法，其中每条边的长度为 -1、0 或 1
Floyd-Warshall algorithm on a directed graph in which every edge's length is either -1, 0, or 1
我正在上Algorithms: Design and Analysis II课程，其中一题如下：
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
提到的讲座视频在 YouTube 上。供参考，算法如下：
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]}
正确答案是第一个，2^n，提示说可以用归纳法证明。我似乎无法理解它。有人可以帮我理解吗？
考虑所有节点都连接到边长为 -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。
我正在上Algorithms: Design and Analysis II课程，其中一题如下：
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 thatGis strongly connected, with at least oneu-vpath for every pairu,vof vertices. The graphGmay or may not have a negative-cost cycle. How large can the final entriesA[i,j,n]be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual,ndenotes|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
提到的讲座视频在 YouTube 上。供参考，算法如下：
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]}
正确答案是第一个，2^n，提示说可以用归纳法证明。我似乎无法理解它。有人可以帮我理解吗？
考虑所有节点都连接到边长为 -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。