关于9.4节中Bellman-Ford的算法

Question

1 2 3 4 5 6 7 8 9 10

for (int pass = 1; pass < G.V(); pass++){     for (int i = 0; i < G.V(); i++){         typename Graph::adjIterator adj(G, i);         for (Edge<Weight>* e = adj.begin(); !adj.end(); e = adj.next())             if (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]){                 distTo[e->w()] = distTo[e->v()] + e->wt();                 from[e->w()] = e;             }     } }

这一段代码中，循环了V-1次松弛操作，为什么每次松弛操作都是对所有点的，而前面讲解的时候说的是V-1次应该对应了从起点开始V-1步可以到达的点，感觉逻辑有点对不上。按前面讲的逻辑，应该是类似于递归的方式

Answer 1

liuyubobobo 2017-04-10 02:35:00

非常感谢你的问题。因为你的问题我又重新review了一遍我的bellman-ford代码，确实有一些bug。我已经修复了。在这里尝试重新讲解一遍代码。

一般简单的实现Bellman-Ford算法（包括之前的Dijkstra算法），都是用MAX_INT的值来表示无穷。这样如果distTo[x] = MAX_INT，就表示从起始点s到x这个点还不可达。基于这样的想法Bellman-Ford算法可以这样来写：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

// 以下内容为伪码理解意思即可...   // 初始化起始点s到其余所有点i均不可达, 其距离为MAX_INT for( int i = 0 ; i < V ; i ++ )        distTo[i] = MAX_INT;           distTo[s] = 0;    // 起始点s到自己的距离为0       // Bellman-Ford的过程 // 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离   for( int pass = 1 ; pass < G.V() ; pass ++ ){         // 每次循环中对所有的边进行一遍松弛操作        for( e in E )            if( distTo[e->v()] + e->wt() < distTo[e->w()]) )                 distTo[e->w()] = distTo[e->v()] + e->wt();    }

上面的代码由于使用伪码，所以代码行数比较少，思路看起来应该更清晰。这里注意：在Bellman-Ford的pass那重循环里，由于distTo初始使用了MAX_INT，所以我们可以很方便的直接判断 if( distTo[e->v()] + e->wt() < distTo[e->w()]) ) 。但是在实际情况下，使用MAX_INT有很多不方便的地方（比如容易整型溢出）。因为在计算机里，这个数字毕竟不是真正的“无穷”。所以在我们课程的代码里，可以使用from这个数组来看：对于每一个e，e->v()这个节点是否在之前的遍历中已经可达了。如果是已经可达的节点，才可以进一步判断当前是否可以进行这个松弛操作。在我课程讲解的代码中缺少了对e->v()这个节点是否可达的判断。

另外，你观察到在我们的课程代码中，第二重循环又对所有的顶点进行了一次遍历。这其实是基于我们自己实现的这个Graph类，尝试对图中的所有边进行遍历的方式：先遍历所有顶点，再遍历所有顶点对应的邻边。使用这样的方式，对于无向图来说，其实每个边都被遍历了两次，不过这个小问题并不影响整个算法的正确性。如果有兴趣，也可以思考一下为Graph类添加一个针对图中所有的边进行遍历的迭代器：）是一个不错的练习，也能加深对迭代器的认识：）

我修改过的Bellman-Ford代码如下，加入了更多注释。希望你可以理解，有任何问题随时交流：）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

BellmanFord(Graph &graph, int s):G(graph){               this->s = s;         distTo = new Weight[G.V()];         // 初始化所有的节点s都不可达, 由from数组来表示     for( int i = 0 ; i < G.V() ; i ++ )            from.push_back(NULL);               // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0        distTo[s] = Weight();         from[s] = new Edge<Weight>();  // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉             // Bellman-Ford的过程     // 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离     for( int pass = 1 ; pass < G.V() ; pass ++ ){             // 每次循环中对所有的边进行一遍松弛操作          // 遍历所有边的方式是: 先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边         for( int i = 0 ; i < G.V() ; i ++ ){                 // 使用我们实现的邻边迭代器, 遍历和所有顶点相邻的所有边             typename Graph::adjIterator adj(G,i);                   for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )                     // 对于每一个边首先判断e->v()可达                 // 之后看: 如果e->w()以前没有到达过, 显然我们可以更新distTo[e->w()]                 // 或者e->w()以前虽然到达过, 但是通过这个e, 我们可以获得一个更短的距离,                  // 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]                 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;                     }             }         }           hasNegativeCycle = detectNegativeCycle();     }

同时，课程的官方github代码进行了更新。有兴趣可以查阅：

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

再次感谢你的问题。非常抱歉我的代码中的bug让你困惑了。如果愿意，可以加我的微信：liuyubobobo。请注明慕课网算法课程，我会发给你一个小红包：）

• 提问者 王海龙123 #1

  非常感谢！

Answer 2

liuyubobobo 2017-03-31 20:57:23

bellman-ford算法的第pass次循环找到了从起始点到其他点，最多使用pass步可到达的最短距离，但由于Bellman-Ford算法可以处理带有负权边的图，所以再下一次循环中，从起始点到其他点使用pass+1步，有可能获得一个更短的距离。因此，我们在每一次循环中，都不能保证找到了从起始点到某些点的最短距离，也就不能放弃其他点。所以每一次循环，所有的点都需要再考虑一次，找到从起始点到所有其他点，最多使用pass+1步可到达的最短距离。直至最后，我们找到了从起始点，到所有其他点，最多使用V-1步的最短距离。到这里，我们可以说找到了起始点到所有其他点的最短距离，这是因为在一个联通图中，从一个点到另外一个点，最多需要走V-1步，即所有其他节点都走一遍。

不过，Bellman-Ford算法确实可以优化。不妨在网上搜搜看：）其中，你可能会找到一个叫做SPFA的算法，是基于Bellman-Ford的思路做的改进。值得骄傲的是，SPFA算法是西南交通大学段凡丁于1994年发表的一个算法：）

• 提问者 王海龙123 #1

  老师我有些不理解的是循环for (int i = 0; i < G.V(); i++)，这个循环的意思不是遍历所有顶点，然后找到每个顶点对应的边吗？而在循环里面写的是typename Graph::adjIterator adj(G, i);，是第i个顶点啊，而不是从起点开始第i步可以到达的点啊。

• liuyubobobo 回复 提问者 王海龙123 #2

  hello，我理解你的问题，我最近有些忙，你的这个问题有点儿大，我尽快抽时间整理一下代码回复你，带来不便，非常抱歉！

• 提问者 王海龙123 回复 liuyubobobo #3

  回复 liuyubobobo多谢老师

点开查看后面7条评论

Answer 3

ShiveryMoon 2017-11-20 01:01:15

关于你的问题里，‘循环了V-1次松弛操作，为什么每次松弛操作都是对所有点的’

事实上BellmanFord算法就是这么蠢。

而就像老师说的，spfa算法就是在这里对bellmanford算法进行了优化，它只松弛‘第pass次遍历可以到达的点’

回答有误请见谅

• liuyubobobo #1

  大赞！：）

Answer 4

提问者 王海龙123 2017-03-31 20:37:29

distto数组对应的距离应该是从起点到index点的距离，比如在第一次循环（pass=1）中，对所有点更新进行更新的时候，如果i点与起点不相连的话，此时与i点相连的点的距离有可能被更新为dist[i]+e-wt()，这时的distto并不是到起点的距离啊，在后面的循环中又为什么作为比较的项呢

• liuyubobobo #1

  为了不让别的同学迷惑，以为这个问题是一个后续问题，在这里再回复一下：）请看我更新的代码。进行松弛操作的条件是：对于e: v->w，我们已经求出了从起始点，到v的最短距离，即起始点到v已经相连了。这就是31行的 if( from[e->v()] ...  这个条件的意思：）