关于Bellman-Ford的过程

Question

刘老师我一直不太明白 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;    

                }    

        }    

Answer 1

liuyubobobo 2018-01-26 04:18:45

首先非常抱歉，这个课程视频里我的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算法还可以优化，在上面我提到的问答里，包括其中的别的同学的讨论里，也提到了。有兴趣可以深入研究看：）

• 提问者 慕UI5584032 #1

  bobo老师，我还是不太理解 对所有的点进行V-1次松弛操作，理论上就找到从源点到其他所有点的最短路径这句话的含义，逻辑上老是连不上，你能用更直接的方式来解释这个含义嘛，谢谢了

• liuyubobobo 回复 提问者 慕UI5584032 #2

  松弛操作是在找：经过更多边，但是距离却更短的路径。每多做一次松弛操作，就是在找多添加一条边以后的更短路径。一个图如果有V个顶点，从源点s到任一点，最多经过V-1条边（即所有V个节点都走一遍）。所以进行V-1次松弛操作以后，就找到了从源点出发，到任一点，最多包含V-1条边的最短路径。

• 提问者 慕UI5584032 回复 liuyubobobo #3

  bobo老师我看你视频教程图例和代码所表达的东西不一致，图例当中，是0->1,0->2，0->3算是一次pass循环,然后1->2,2->3算入第二次pass循环，代码如果我没有理解错的话，是每次pass循环，都对全体顶点进行一个遍历，即第一次pass循环的结果0->1,0->2,0->3,1->2,1->4,2->3,2->4,4->3，完全形成了最短路径，后面几次只是不断重复原来已经形成的最短路径嘛。。

点开查看后面4条评论