贝尔曼-福德算法和一道奥林匹克问题？

Question

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

我们知道Bellman-Ford算法在每一步都检查所有边，对于每条边，如果满足以下条件：

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

则更新d(v)，其中w(u,v)是边(u, v)的权重，d(u)是顶点u的最佳路径长度。如果在一步中我们没有更新顶点，则算法终止。假设这个算法用于在图G中从顶点s找到所有最短路径，在执行k

1.从s到所有最短路径上的边数最多为k-1 2.从s到所有最短路径的权重最大为k-1 3.图形没有负循环。

有谁可以讨论这些选项吗？

- user4591951

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，这说明该循环是非负的。

- David Eisenstat

---

你能否回复我的评论？ - user4591951

@MaryamGhizhi 写出总和。取消掉那些会抵消的项，例如“-d(v4) + d(v4)”。 - David Eisenstat

能否简单地描述一下它？ - user4591951

@MK 这里有两个不同的问题。 p. 295，Bellman-Ford 的未优化版本是我所指的“同时松弛”版本。早期终止是一种不同的优化——因为 Bellman-Ford 的每轮操作都相同，如果我们在整个轮次中没有进行任何更改（对于同时或非同时版本都无关紧要），那么显然所有后续轮次也不会进行更改，因此我们可以停止运行。 - David Eisenstat

@MK 是的，更准确地说，Bellman-Ford找到的每条最短路径长度都不超过k，其中k是完成的轮数。 - David Eisenstat

Answer 2

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

- Dipu Pandey