bellman-ford

来源:9-5 负权边和Bellman-Ford算法

gotodream

2019-06-07

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这层循环
写回答

1回答

liuyubobobo

2019-06-08

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

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


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

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


继续加油!:)

0
0

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程