Bellman-Ford和有关Graph G的一些事实?

2015-03-28 math graph graph-theory shortest-path bellman-ford

我们知道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-1

2)从s的所有最短路径的权重最大为k-1

3)图没有负周期。

我确定其中之一是正确的,但是我的助教说其中两个是正确的。对这些问题有什么想法或提示吗?

Answers

让我们一次浏览一个语句:

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

考虑下图:

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

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

2)从s的所有最短路径的权重最大为k-1

边缘的数量或它们的总重量均不受k-1限制。考虑上例中的所有边的权重为1000。很明显,与k没有关系。

3)图没有负周期。

如果按您的定义算法(在不进行任何更改时终止),那么这是正确的。任何负周期都将导致无限循环,因为此循环中顶点的距离连续减小。

Related