1回答

liuyubobobo

2019-03-20

已采纳

首先，请注意，视频中的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

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

加油！：）

0

3

Poplar_hills

多谢老师！

2019-03-20

共3条回复