我们知道 bellman-ford 算法检查每一步中的所有边，并且对于每条边，如果，
d(v)>d(u)+w(u,v)
然后 d(v) 被更新，使得 w(u,v) 是边 (u, v) 的权重，d(u) 是顶点的最佳查找路径的长度u。如果在一个步骤中我们没有更新顶点，则算法终止。假设该算法，在迭代完成后，找到从s图 G 中的n顶点到顶点的所有最短路径k<n，以下哪项是正确的？
1) 所有最短路径中的边数
s最多为k-12）所有最短路径的权重
s最多为k-13）图没有负循环。
我确定其中一个是正确的，但我的助教说其中两个是正确的。对这些问题有任何想法或提示吗？
让我们一次一个地看一下这些陈述：
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
边的数量和它们的总权重都不受 限制k-1。考虑上例中的所有边的权重为 1000。很明显，与 没有任何连接k。
3）图没有负循环。
如果您像以前一样定义算法（在没有进行任何更改时终止），那么这是正确的。任何负循环都会导致无限循环，因为该循环中顶点的距离会连续减小。