Bellman-Ford和关于图G的一些事实

Question

我们知道bellman-ford算法在每个步骤中检查所有边，对于每个边，如果，

d（v）>d（u）+w（u，v）

则更新d（v），使得w（u，v）是边（u，v）的权重，并且d（u）是顶点u的最佳查找路径的长度。如果在一个步骤中，我们没有更新顶点，则算法终止。假设这种算法，对于在k<n迭代完成后，从图G中的顶点s到n的所有最短路径，以下哪一个是正确的？

1） 从s开始的所有最短路径中的边数最多为k-1

2） 来自s的所有最短路径的权重至多为k-1

3） 图形没有负循环。

我确信其中一个是真的，但我的助教说其中两个是正确的。对这些问题有什么想法或暗示吗？

Answer 1

让我们一次看一个语句：

1） 从s开始的所有最短路径中的边数最多为k-1

考虑下图：

s ---e1---> n1 ---e2---> n2 ---e3---> n3

如果边按给定顺序排列（e1, e2, e3），则在第一次迭代后，每个节点都将具有正确的距离（检查e1更新n1，然后检查e2更新n2，依此类推）。因此，在这种情况下，算法在k=2迭代后停止，因为第二次迭代不会改变任何内容。最长最短路径中的边数为3，并且3 <= 2-1不成立。因此，这种说法是错误的。但是，如果同时计算所有边，则该语句是正确的（每次迭代只能比上一次迭代更远一条边）。

2） 来自s的所有最短路径的权重至多为k-1

边的数量和它们的总重量都不受CCD_ 21的限制。考虑以上示例中的所有边的权重为1000。很明显，不存在与k的连接。

3） 图形没有负循环。

如果您像以前那样定义算法（在没有进行任何更改时终止），那么这是正确的。任何负循环都会导致无限循环，因为循环中顶点的距离会依次减小。