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。假设该算法在 k < n 次迭代完成后找到图 G 中顶点 s 和 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，这表明循环是非负的。

Answer 2

我认为选项 3 是不正确的，因为要知道是否存在负权重循环，Bellman ford 算法需要 运行 n 次。 首先 n-1 次计算最短路径，然后再检查一次距离是否有任何改进，如果有改进，则表示存在负权重循环。