行李员福特和一个奥林匹克竞赛的问题？
行李员福特和一个奥林匹克竞赛的问题？
提问于 2015-04-09 00:42:21
我三天前参加了奥林匹克竞赛考试。我遇到了一个很好的问题，如下所示。
我们知道贝尔曼-福特算法在每一步中检查所有的边，并且对于每条边，
d( v) >d(u)+w(u，v)
然后更新d(v)，使得w(u,v)是边(u, v)的权重，d(u)是顶点u的最佳发现路径的长度。如果在一个步骤中我们有了no update for vertexes，算法就是terminates。假设在k < n迭代完成后，这个算法用于在具有n个顶点的图G中找到从顶点s到所有最短路径的所有最短路径，下面哪一个是正确的？
距离s的所有最短路径中的
- 边数最多为
k-1
从s到所有最短路径的
- 权重最多为
k-1
- 图没有负循环。
谁可以讨论这些选项？
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-04-09 00:51:26
%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，这表明该周期是非负的。
Stack Overflow用户
发布于 2016-11-13 01:16:58
我认为选项3是不正确的，因为要知道是否存在负权重循环，Bellman ford算法需要运行n次。首先n-1次计算最短路径，然后再一次检查距离是否有任何改善，这意味着存在负权重循环。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29520550
复制相关文章
相似问题