采纳答案成功!
向帮助你的同学说点啥吧!感谢那些助人为乐的人
这个BellmanFord算法是不是要要求从节点s开始能到达所有的结点?
当我对这张图以节点3作为源调用BellmanFord算法的时候,运行出来,程序提示存在负权环。(使用的是已经勘误了的代码)
嗯,我的代码确实还有不严谨的地方。在这种情况下提示“存在负权环”确实是不对的。我们的检验负权环的代码应该是基于整个图是已经联通的情况下进行的。这也是为什么我们的最短路径算法例存在 bool hasPathTo( int w ) 这个接口。我们在检查最短路径前,应该首先查看是否存在从源点到这个点的路径。为此,我在我的代码上在查找最短路径前,assert了首先需要有路径。
// 返回从s点到w点的最短路径长度
Weight shortestPathTo(
int
w ){
assert
( w >= 0 && w < G.V() );
( hasPathTo(w) );
( !hasNegativeCycle );
return
distTo[w];
}
在调用代码的过程中,用户也应该首先确定存在路径,再查看最短路径是什么。这就好比我们调用数组的某一个元素,首先应该确保我们调用的索引不越界,在查看这个索引对应的元素是什么。
for
(
i = 1 ; i < V ; i ++ ) {
if
(bellmanFord.hasPathTo(i)) {
// 首先要确保有通路
cout <<
"Shortest Path to "
<< i <<
" : "
<< bellmanFord.shortestPathTo(i) << endl;
bellmanFord.showPath(i);
else
"No Path to "
<< i << endl;
"----------"
<< endl;
感谢你的问题,我又精炼了整个课程的代码:)
非常感谢!
谢谢你的问题,让这个课程的代码更加丰富严谨了。如果有时间,可以加我的微信:liuyubobobo 我会发给你一个小红包:)
登录后可查看更多问答,登录/注册
课程专为:短时间内应对面试、升职测评等艰巨任务打造
9.0k 21
5.8k 3
5.1k 5
1.5k 18
购课补贴联系客服咨询优惠详情
慕课网APP您的移动学习伙伴
扫描二维码关注慕课网微信公众号