algorithm - Bellman Ford 和 One Olympiad 问题？

Question

我三天前参加了奥林匹克考试。我遇到了一个很好的问题，如下所示。

我们知道 bellman-ford 算法会检查每一步中的所有边，并且对于每条边，如果，

d(v)>d(u)+w(u,v)

然后 d(v)正在更新 w(u,v)是边的权重 (u, v)和 d(u)是顶点的最佳查找路径的长度 u .如果在一步中我们有 no update for vertexes , 算法 terminates .假设此算法用于查找从顶点 s 开始的所有最短路径在图 G 中 n k < n 之后的顶点迭代结束，下列哪项是正确的？

1. number of edges in all shortest paths from s is at most k-1

2. weight of all shortest paths from s is at most k-1

3. Graph has no negative cycle.

谁可以讨论这些选项？

Answer 1

1 是不正确的。首先，我们总是找到具有 k 条边的最短路径(如果有的话)。而且，如果我们碰巧按照最短路径树的拓扑顺序松弛弧，那么我们会在一次迭代中收敛，尽管最短路径树可能有任意深度。

s --> t --> u --> v

Relax s->t, t->u, u->v; shortest path from s->v is three hops,
but B--F has made two iterations.

2 不正确，因为谁知道权重是多少？

  100
s --> t

Relax s->t; weight is 100, but B--F has made two iterations.

3 是正确的，因为通过平均论证，负循环的至少一个弧会松弛。让v1, ..., vn 成为一个循环。由于弧是松弛的，我们有 d(vi) + len(vi->vi+1) - d(vi+1) >= 0。对所有 i 的不等式求和并伸缩 d 项以简化为 sum_i len(vi->vi+1) >= 0，其中表示循环是非负的。