关于9.4节的Bellman-Ford算法

Question

这个BellmanFord算法是不是要要求从节点s开始能到达所有的结点？

当我对这张图以节点3作为源调用BellmanFord算法的时候，运行出来，程序提示存在负权环。（使用的是已经勘误了的代码）

Answer 1

liuyubobobo 2017-05-13 12:22:20

嗯，我的代码确实还有不严谨的地方。在这种情况下提示“存在负权环”确实是不对的。我们的检验负权环的代码应该是基于整个图是已经联通的情况下进行的。这也是为什么我们的最短路径算法例存在 bool hasPathTo( int w ) 这个接口。我们在检查最短路径前，应该首先查看是否存在从源点到这个点的路径。为此，我在我的代码上在查找最短路径前，assert了首先需要有路径。

// 返回从s点到w点的最短路径长度    
Weight shortestPathTo( int w ){    
    assert( w >= 0 && w < G.V() ); 
    assert( hasPathTo(w) );     
    assert( !hasNegativeCycle );      
    return distTo[w];    
}

 

在调用代码的过程中，用户也应该首先确定存在路径，再查看最短路径是什么。这就好比我们调用数组的某一个元素，首先应该确保我们调用的索引不越界，在查看这个索引对应的元素是什么。

for( int i = 1 ; i < V ; i ++ ) {    
    if (bellmanFord.hasPathTo(i)) {  // 首先要确保有通路    
        cout << "Shortest Path to " << i << " : " << bellmanFord.shortestPathTo(i) << endl;    
        bellmanFord.showPath(i);    
    }    
    else    
        cout << "No Path to " << i << endl;    
    cout << "----------" << endl;    
}

 

感谢你的问题，我又精炼了整个课程的代码：）

• 提问者 timpcfan #1

  非常感谢！

• liuyubobobo 回复 提问者 timpcfan #2

  谢谢你的问题，让这个课程的代码更加丰富严谨了。如果有时间，可以加我的微信：liuyubobobo 我会发给你一个小红包：）