文章目录
开始之前
本Blog之前已经介绍过一种单源最短路算法——Dijkstra算法。但Dijkstra算法也有着自己的缺点，其中最明显的问题就是无法处理带负权边的图，其原因与其算法中包含的贪心原理有关。
而接下来介绍的算法，则拥有处理负权边的能力，该算法就是Bellman Ford单源最短路算法。该算法的核心思想是，对图中的每条边，都进行足够次数的Relaxation（松弛）操作，从而逐步推导出每个点距离出发点都最短路径长度。
关于Bellman Ford算法的原理和代码实现，网络中已有大量优秀的资料，这里便不再说明算法本身的详细工作流程。接下来着重说明一些Bellman Ford算法中一些限制条件，及其相关的一些理解。
Bellman Ford算法特性
当出现负权回路时…
在通过Bellman Ford算法计算单源最短路时，会要求所计算的图中不得存在权值为负值的回路。这个限制相对较好理解，下面举一个简单的例子。
如图，图中的A->B->C->A便是一个负权回路。而假设我们现在需要以A点作为出发点计算最短距离，请问A->D的最短距离应该是多少？不难发现这里出现了死循环。我们可以从原点出发，不停的走A->B->C->A这条路，每循环一次，我们距离出发点的距离就会越来越小。这也就意味着，只要我们的路径不断的在负权回路中重复足够多次，每一个点距离出发点的距离都可以认为是无穷小，这显然是不合理的。
负权回路对于图来说是存在特殊意义的，比如在经济学的部分领域中，“负权回路”是一个非常具有吸引力的词，因为可能代表着可持续的收益链，也可以代表着套利的机会，但Bellman Ford不认这些，在单元最短路算法的世界中，我们暂且不接受“套利机会”的存在。也就是说我们不允许待处理的图中出现负权回路，以此来保证计算结果是有意义的。
对于Bellman Ford算法的一些理解
迭代次数的理解
Bellman Ford算法的核心思想，在于每迭代一次，就对所有边进行遍历，并执行Relaxation操作。这里不难发现，迭代k次时，得到的结果，可以保证至少是路径条数为k时的最优解。
为什么说是至少呢，因为其遍历的结果可能跟边遍历的顺序有关，如下图：
如图，我们发现对于图中的无向图，如果从左边的边开始遍历，实际上遍历一次之后我们就已经得到了最优解。而如果从右边开始遍历，我们就需要遍历3次才能得到最优解。
按照这个思路理解，不难推出，遍历k次时，得到的答案，只能保证，至少是路径条数为k限制下的最优解。
这里对路径条数做出说明，一个路径由多个边组成，上方所说的“路径条数”，指的是对于某条路径，其经过的边的个数的和。
为什么迭代次数等于点的个数？
上方我们已经论述了迭代次数k的意义，迭代k次时，得到的结果至少是路径条数k情况下的最优解，部分点的数据可能比会更优，但对于所有的点，只能保证其为路径条数k情况下的最优解。
那么我们到底需要迭代几次呢？根据定义，我们将问题转换成为：对于一个无向图，其某个点A到某个点B的全局最优路径中，最多可能经过几条边。
经过思考之后发现，最坏情况下，最优路径将会不重复的经过所有点。接下来对这个结论进行简单的说明：
首先是经过所有点。如果我们想要强迫最优路径经过尽可能多的点，最坏的情况之一，便是这个图形成了一个没有分叉的纯线性结构（就像上方对于迭代次数解释时所用图一样，每两个点用一条边链接，总边数为点数-1），这样从最左边到最右边的点，最优路径边毋庸置疑是经过所有的点。
其次是不重复。为什么我们可以确保最优路径中不会重复经过同一个点呢？这从某个角度上来说得益于算法前面的一个前提条件——不允许负权回路。想象一下，如果路径重复经过了同一个点，说明这个路径必定存在一段回路（从重复点出发，经过某个路径，又回到重复点）。而此时如果这个回路确定不是负权回路，那么说明如果跳过这段回路，我们可以得到一个权重更短的路径，反向说明了目前的路径不是最优路径。因而可以确定，如果一个路径被确定为最优路径，且该图中没有负权回路，那么这个路径绝对不会重复经过同一个点。
说明完毕，接下来让我们看看这两个结论，不难发现，不重复经过所有点，那么对于一个点个数为N的图，符合条件的路径，最长只能是N-1（因为一旦大于N-1，说明必定要产生回路，与条件冲突），所以最终确定，如果需要得到全局最优，其最少迭代次数为N-1。
综上所述，容易得到，算法的时间复杂度为O(N*M)。其中，N为点的个数，M为边的个数。
为什么它能攻克负权边？
在Dijkstra算法的文章中，笔者提到了一个观点，Dijkstra的核心是基于贪心的，而贪心带来了局部最优解这一隐患。带着这个角度再来看Bellman Ford算法，是否有一种熟悉的感觉？Bellman Ford算法的每次迭代都基于上一次的迭代结果。先知道路径条数1情况下的最优解，再根据此状态推出条数2情况下的解，以此类推最终得到路径条数为N-1时的最优解（也就是全局最优解），是不是有点「动态规划」的味道了呢？正是借助这这种工作模式，不像Dijkstra算法一样看到一点点甜头就着急的把点Close掉，Bellman Ford拥有了不被眼前甜美假象迷惑的能力，坚持着自己的本分，不断想着正确的道路一步步迈进，最终终于得到了令人满意的结果。
发表回复
要发表评论，您必须先登录。