SPFA算法详解

前置知识：Bellman-Ford算法
前排提示：SPFA算法非常容易被卡出翔。所以如果不是图中有负权边，尽量使用Dijkstra！(Dijkstra算法不能能处理负权边，但SPFA能)
前排提示*2：一定要先学Bellman-Ford！
0.引子
在Bellman-Ford算法中，每条边都要松弛/(n-1/)轮，还不一定能松弛成功，这实在是太浪费了。能不能想办法改进呢？
非常幸运，SPFA算法能做到这点。(SPFA又名“Bellman-Ford的队列优化”，就是这个原因。)
1.基本思想
先说一个结论：只有一个点在上一轮被松弛成功时，这一轮从这个点连出的点才有可能被成功松弛。
为什么？显而易见
好吧其实我当初也花了不少时间理解这玩意
松弛的本质其实是通过一个点中转来缩短距离(如果你看了前置很容易理解)。所以，如果起点到一个点的距离因为某种原因变小了，从起点到这个距离变小的点连出的点的距离也有可能变小(因为可以通过变小的点中转)。(通读三遍再往下看)
所以，可以在下一轮只用这一轮松弛成功的点进行

SPFA算法详解最先出现在Python成神之路。