bellman-ford

Question

for( int i = 0 ; i < G.V() ; i ++ ){

        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;    

            }    

    }    
    我怎么感觉这个已经可以输出正确结果了为什么还要最外面的pass 这一层循环啊
    好像不用pass这层循环。而且如果这个没有最外面的一层循环这两层循环不是也做了松弛操作吗，假设0->2(2)用0->5->2不就是松弛吗想不通为什么要用pass这层循环

Answer 1

liuyubobobo 2019-06-08 00:46:37

里面的两层循环只对所有的边进行了一轮松弛操作；

bellman-ford算法要对所有边进行V-1轮松弛操作。

可以参考这个问答，在这里我举了一个例子，进行一轮松弛操作是不够的：）

https://coding.imooc.com/learn/questiondetail/40710.html

继续加油！：）