关于Bellman-Ford的过程
来源：9-5 负权边和Bellman-Ford算法
慕UI5584032
2018-01-26
刘老师我一直不太明白 Bellman-Ford算法最外层for循环的意思，里面for循环可以走完逻辑的，比如最简单的1->3(5),1->2(6),2->3(-2)这个图，按照您的代码
for( int i = 0 ; i < G.V() ; i ++ ){
(这个循环不就是遍历出三个点的全部边了嘛，然后下面逻辑判断的结果是2次松弛操作，最终得到最短路径1->2->3，另外得到最短路径后，原路径在下次循环的话还需要在继续遍历出来嘛)
typename Graph::adjIterator adj(G,i);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
if( from[e->v()] &&
(!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
distTo[e->w()] = distTo[e->v()] + e->wt();
from[e->w()] = e;
}
}
1回答
-
首先非常抱歉，这个课程视频里我的bellman-ford代码稍微有些问题。请参考这个问答，里面有详细的说明：https://coding.imooc.com/learn/questiondetail/7968.html
总体来说，bellman-ford的外层循环的意思是：进行V-1次循环，每一次都求出从起始点，经过i步可以到达的节点的最短距离。所以，我们这层循环最多执行V-1步即可。因为我们的图一共有V个节点，从起始点到图中另一个节点，最多只需要经过V-1步。（仔细比较一下我的代码，也是为了表达这个意思，循环变量我起名为pass，是从1开始循环的）
至于你举得例子，由于很简单，没有反应出所有可能的情况。试一下这个例子：
1->3(-2)
2->1(6)
2->3(5)
起始点是2。
此时，我们在第一重循环是找不到2->1->3这个路径的，必须经过第二轮松弛操作：）希望通过这个例子你可以看出问题在哪里：我们在bellman-ford的算法中是没有控制边松弛的顺序的。我们只是每一轮按照一个固定顺序把所有的边松弛一遍而已。而你给出的例子，其实依赖于在一轮松弛操作中，先处理了1->2，又处理了2->3。这是一种特殊情况。但是为了让所有情况都没有问题，我们最多对所有边做V-1次松弛操作就好了。
当然，bellman-ford算法还可以优化，在上面我提到的问答里，包括其中的别的同学的讨论里，也提到了。有兴趣可以深入研究看：）
472020-07-11
相似问题