松弛操作的对象到底是？

Question

Hi bobo 老师，

在这个回答中您说“对节点2的所有邻边进行relax操作”即松弛操作的对象是某个节点的邻边。而在本节说的却都是对买某个节点进行松弛操作说法不太一致。

不管哪种说法我理解松弛操作都是指“计算经过某个节点到达另一个节点的路径的距离”。比如 A —> B —> C若对顶点 B 进行松弛操作或者说对 B 的邻边进行松弛操作都是指计算经过 B —> C 的路径的距离。不知这样理解是否正确？

另外本节最后10’40’'处分析复杂度时PPT 上说的也是“对所有的节点进行 V-1 次松弛操作”因此复杂度是 O(VE)但如果按照上一节的说法即松弛操作的对象是边那岂不是变成了“对所有边进行 V-1 次松弛操作”这样的话算法复杂度不就变成 O(EE) 了吗？

我也参考了别的文章中对 Bellman-ford 算法的解释其中有一篇的说法就是:

反复对边集 E 中的每条边进行松弛操作使得顶点集V中的每个顶点 v 的最短距离估计值逐步逼近其最短距离。

出处：这里

总结一下我的问题
1. 松弛操作的对象是谁？
2. Bellman-ford 算法是对 V 个顶点进行松弛还是对 E 条边进行松弛还是两种都可以呢？
3. 松弛操作的对象不同会导致算法复杂度不同？

谢谢！

Answer 1

liuyubobobo 2019-03-20 01:34:32

首先，请注意，视频中的Bellman-Ford算法的实现有误（原理讲解无误）。修订后的代码请参考这里：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

相关讨论，可以参考这里：https://coding.imooc.com/learn/questiondetail/7968.html

Bellman-Ford算法我讲的确实不够详细。抱歉了。回答你的问题如下：

1 

对于单次松弛操作，其对象是边。对于一个边，假设叫AB，如果有以下的形态：

  C
 / \
A---B

即从A可以达到B，从A绕经C之后也可以达到B，并且A->C->B的路径长度比A->B要短。我们选择使用A->C->B到达B，这叫做一次松弛操作。如果你将A-C, C-B, A-B这三条边看成绳子的话，A-C-B这根绳子显然比AB这根绳子更松：）这叫做边松弛。

对应我们的代码，这是一次边松弛：

// 对e进行松弛操作
if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){    
    distTo[e->w()] = distTo[e->v()] + e->wt();    
    from[e->w()] = e;    
}

 

同时，我们也可以定义点松弛。对一个点进行松弛操作，就是对这个点的所有临边都进行一遍松弛操作。

对应我们的代码，这是一次点松弛。其实，就是在上面的边松弛的基础上，套了一层循环，遍历一个点的所有邻边，对每条边进行松弛操作：）

// 对点i进行松弛操作
typename Graph::adjIterator adj(G,i);    
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )    
    // 对点i的一条临边e进行松弛操作  
    if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){    
        distTo[e->w()] = distTo[e->v()] + e->wt();    
        from[e->w()] = e;    
    }

2

如果理解了上面的两个概念。那么你就会明白，我们说Bellman-Ford算法是对每条边进行松弛，和对每个点进行松弛，是等价的。因为对每个点进行松弛，就是对每个点的所有邻边进行松弛，也就是对所有的边进行松弛操作：）

3

同时，这两种说法对应的算法复杂度是一致的。我们说对所有边进行松弛操作，或者说对所有点进行松弛操作，都是O(E)的：）我们要进行V-1轮松弛操作，每轮操作的复杂度是O(E)的，整体就是O(VE)的：）

关于图论算法的复杂度计算，这个问题可能很普遍：https://coding.imooc.com/learn/questiondetail/101781.html

可以参考，看看对于你理解是否有帮助：）

加油！：）

• 提问者 Poplar_hills #1

  非常感谢老师这么细致的回答?
  
  另外还有个问题想再问一下老师：
  
  对于 Bellman-ford 算法的总体过程是否可以这么理解：对所有边进行一次松弛操作能够确定最小路径树上的一段路径，因为最小路径树最多有 V-1 段，因此需要对所有边进行 V-1 轮松弛操作即可找到完整的最小路径树。
  
  不知这么理解是否正确？
  
  谢谢！

• liuyubobobo 回复 提问者 Poplar_hills #2

  赞！完全正确！V-1就是这么来的！继续加油！：）

• 提问者 Poplar_hills #3

  多谢老师！