2回答

liuyubobobo

2017-10-21

已采纳

首先，非常抱歉，课程中视频介绍的Bellman-Ford算法是有bug的，具体可以参见这个问答下我的回答：http://coding.imooc.com/learn/questiondetail/7968.html 

更新后的代码参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/09-Shortest-Path/Course%20Code%20(C%2B%2B)/05-Implementation-of-Bellman-Ford/BellmanFord.h

希望这个问题解决了你的第一个疑惑。简单来说，如果0和1这两个节点没有直接相连的话，在第一轮循环中，是不会对0-1这条边做松弛操作的。

对你的第二个疑惑，算法在哪里体现了是从s出发？答案就是在算法运行前，我们将distTo[s]设置为了0，同时将from[s]设置为非空。有了这个设置，我们在之后第一轮遍历的时候，将会开始对和s节点相邻的所有边进行松弛操作，从而得到从s开始最多经过一条边到达各个节点所需要的最短路径；之后第二轮遍历，就会得到从s开始最多经过两条边到达各个节点所需要的最短路径；以此类推，直到最后一轮遍历（V-1轮遍历），得到从s开始最多经过V-1条边到达各个节点所需要的最短路径。

可以尝试一下在我们的代码中将起始点改变一下，结果会是不一样的哦：）

1

1

烈焰卡卡

非常感谢！

2017-10-21

共1条回复

烈焰卡卡

提问者

2017-10-20

老师我自己想的解决方案如下，不知道对不对，您看下是否可行：

问题一：再循环每个节点时对from做判断，已经连接的顶点再进行松弛操作，否则跳过。

问题二：在用问题一判断的同时，不判断原点s的from，因为第一次遍历的时候from里都是空，这样使得第一次循环一定是从原点s开始遍历的，这样如果原点设置为2，那么到0没有路径的话，永远也不会对0做松弛操作

0

1

liuyubobobo

非常非常赞！

2017-10-21

共1条回复