1回答

liuyubobobo

2017-05-13

已采纳

嗯，我的代码确实还有不严谨的地方。在这种情况下提示“存在负权环”确实是不对的。我们的检验负权环的代码应该是基于整个图是已经联通的情况下进行的。这也是为什么我们的最短路径算法例存在 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;    
}

 

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

2

2

liuyubobobo

回复

timpcfan

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

2017-05-17

共2条回复