Bellman-ford算法与SPFA算法思想详解及判负权环（负权回路）

我们先看一下负权环为什么这么特殊：在一个图中，只要一个多边结构不是负权环，那么重复经过此结构时就会导致代价不断增大。在多边结构中唯有负权环会导致重复经过时代价不断减小，故在一些最短路径算法中可能会凭借不断重复经过负权环来得到权和为无穷小的最短路径，但因重复经过边不符合简单路径的定义导致这些算法跑最短路时要避免有负权环的出现。

这类算法说的就是Bellman-ford以及基于它进行优化的spfa了。由于负权环的出现导致这些算法的正确性失效。但这世上没有绝对的废物，我们也可以反过来利用这两种算法对负权环的敏感性来判断一个图内有无负权环。

结合一下这两个算法的原理，就能很简单地明白判负权回路的原理了：

    1、Bellman-ford的原理即每次做一次枚举所有边进行一次大松弛操作后必有所有最短路径的第一条边（起点为源点的边）被确定（尽管我们并不确切地知道是哪一条边），被确定后，则会凭这条边再下一次大松弛操作再确定第二条边，以此类推。由于n个点的图的两点间最短路径最长有n条边，所以最多要n次大松弛就能把一个单源最短路求出（但实际上很多时候不到n次大松弛操作，就没有可松弛的了，即已经找到答案，可记录当前大松弛是否做过松弛操作，或基于该缺点改进为spfa）。但如果发现在n次大松弛操作后还有松弛操作可做，就说明负权回路出现了。时间复杂度O（nm）（m为边数），有点大。

    2、SPFA则为针对Bellman-ford的缺点做的使每次做的松弛操作更有效的优化。发现在Bellman-ford第一次大松弛中只有松弛从源点出来的边才是有效的，松弛时当边的起点有效（被松弛过）时松弛操作才有效。那我们就不妨每次都只做有效的松弛操作，建一个队列，开始时将源点入队，每次从队头弹出head，尝试松弛所有head的邻接点，若松弛成功且该邻接点不在队中，就把它入队；否则什么也不干。时间复杂度为O（vm），v是一个平均值为2的常数。（因为当我们每次都做有效的松弛操作时，就会发现跑最短路快了很多，在大多数情况下可以吊打各个最短路算法。当然也特别容易被特殊数据卡，此时时间复杂度容易退化为O(nm)）。类似的，spfa每做“一层”（层的概念类似于BFS的层）松弛操作就会确定所有最短路的一条边，故最极限的情况spfa做n层松弛操作就可以求出一个单源最短路了。

　　　　每层松弛操作只会导致一个点最多出队一次，由于最多只有n层，所以每个点的出队次数最多应不超过n。不幸的是，spfa的松弛操作碰上负权环时，会发现，从环的某一点a开始松弛其他点时，由于是负权环，所以绕了一圈回来后一定会发现a要被松弛为更小的值b（环外的点松弛环上的点只会使b更小），故就有无限循环松弛出现。记录每个点的出队次数，当发现有一个点的出队次数大于n，即为有负权环出现了。

善意的提醒：解题推理时从某个结构的基础组成部分入手并扩展，常常遇到惊喜~~~

原文：https://www.cnblogs.com/InductiveSorting-QYF/p/11246388.html