关于9-4节Bellman Ford算法两个问题

Question

第一个问题：想知道每一轮循环中要对所有的顶点做松弛操作，假如第一轮循环该对1这个顶点做松弛操作，但1这个顶点并没有和0这个节点直接相连，这时distTo【1】+ -4  肯定要小于distTo【2】，这样算法岂不是就出现问题了，是不是对这样还未访问的顶点再依次循环遍历的时候应该跳过？

第二个问题：感觉整个算法并没有体现出从原点s出发找最短路径，如果我把原点设置为2，那么最终distTo和fromed应该是和原点为0时一样吧

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

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

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

Answer 1

liuyubobobo 2017-10-21 06:52:26

首先，非常抱歉，课程中视频介绍的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

  非常感谢！

Answer 2

提问者 烈焰卡卡 2017-10-20 14:54:27

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

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

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

• liuyubobobo #1

  非常非常赞！