深入理解spfa算法是如何优化bellman-ford的

原文：https://blog.csdn.net/u011893609/article/details/81232124 

前言

Bellman-Ford算法，限于资料匮乏和时间复杂度比Dijkstra算法高，包括白书在内的很多资料，都没说得太明白。对于优化后的SPFA算法也没有提及。

而且最短路问题通常是作为图论的入门问题，学习者通常没有图论基础，不知道图论的一些基本常识，看已有的资料很容易产生疑惑。其实，从Bellman-ford算法优化到SPFA算法实际上是顺理成章的。

Bellman-Ford算法有什么用。

Bellman-Ford算法是用来解决单源最短路问题的。

在现实生活旅游途中，我们通常想知道一个景点到其他所有景点的最短距离，以方便我们决定去哪些比较近的景点。而这时候，Bellman-Ford算法就有用了。

Bellman-Ford算法的优点是可以发现负圈，缺点是时间复杂度比Dijkstra算法高。

而SPFA算法是使用队列优化的Bellman-Ford版本，其在时间复杂度和编程难度上都比其他算法有优势。

算法流程

（1）初始化：将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0

（2）迭代：遍历图中的每条边，对边的两个顶点分别进行一次松弛操作，直到没有点能被再次松弛

（3）判断负圈：如果迭代超过V-1次，则存在负圈

总结

定理一：只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作

迭代的实际意义：每次迭代k中，我们找到了经历了k条边的最短路。

“没有点能够被松弛”时，迭代结束

根据定理一“只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作”，似乎算法中遍历每条边的做法比较菜，我们只需要考虑那些被成功松弛的点的邻点不就好了吗？答案是肯定的。我们可以简单地通过一个队列来维护这些被成功松弛的点，这个小小的改进可以带来巨大加速，改进之后的算法被称为SPFA。

直观理解负圈

符合常识地，有定理二：如果在边权都为正的图中，最短路一定是一条路径，而不是一个圈，且长度不会大于等于V

拓展到存在负边权的图中，有定理三：对于存在负圈的图，最短路无意义

定理四：对于不存在负圈的图，最短路一定是一条路径，且长度不会大于等于V