系列文章目录
单源最短路径（1）：Dijkstra算法 单源最短路径（2）：Bellman_Ford算法 单源最短路径（3）：SPFA算法 单源最短路径（4）：总结
SPFA（Shortest Path Faster Algorithm）算法，是西南交通大学段凡丁于1994年发表的，其在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。
设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点u，并且用u点当前的最短路径估计值dist[u]对与u点邻接的顶点v进行松弛操作，如果v点的最短路径估计值dist[v]可以更小，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。（所谓的松弛操作，简单来说，对于顶点i，把dist[i]调整更小或更大。更多解释请参考百科：松弛操作)
而其检测负权回路的方法也很简单，如果某个点进入队列的次数大于等于n，则存在负权回路，其中n为图的顶点数。
/**
*
* author : 刘毅（Limer）
* date : 2017-05-28
* mode : C++
*/
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int matrix[100][100]; // 邻接矩阵
bool visited[100]; // 标记数组
int dist[100]; // 源点到顶点 i 的最短距离
int path[100]; // 记录最短路的路径
int enqueue_num[100]; // 记录入队次数
int vertex_num; // 顶点数
int edge_num; // 边数
int source; // 源点
bool SPFA()
{
memset(visited, 0, sizeof(visited));
memset(enqueue_num, 0, sizeof(enqueue_num));
for (int i = 0; i < vertex_num; i++)
{
dist[i] = INT_MAX;
path[i] = source;
}
queue<int> Q;
Q.push(source);
dist[source] = 0;
visited[source] = 1;
enqueue_num[source]++;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
visited[u] = 0;
for (int v = 0; v < vertex_num; v++)
{
if (matrix[u][v] != INT_MAX) // u 与 v 直接邻接
{
if (dist[u] + matrix[u][v] < dist[v])
{
dist[v] = dist[u] + matrix[u][v];
path[v] = u;
if (!visited[v])
{
Q.push(v);
enqueue_num[v]++;
if (enqueue_num[v] >= vertex_num)
return false;
visited[v] = 1;
}
}
}
}
} // while (!Q.empty())
return true;
}
void Print()
{
for (int i = 0; i < vertex_num; i++)
{
if (i != source)
{
int p = i;
stack<int> s;
cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是： ";
while (source != p) // 路径顺序是逆向的，所以先保存到栈
{
s.push(p);
p = path[p];
}
cout << source;
while (!s.empty()) // 依次从栈中取出的才是正序路径
{
cout << "--" << s.top();
s.pop();
}
cout << " 最短路径长度是：" << dist[i] << endl;
}
}
}
int main()
{
cout << "请输入图的顶点数，边数，源点：";
cin >> vertex_num >> edge_num >> source;
for (int i = 0; i < vertex_num; i++)
for (int j = 0; j < vertex_num; j++)
matrix[i][j] = (i != j) ? INT_MAX : 0; // 初始化 matrix 数组
cout << "请输入" << edge_num << "条边的信息：\n";
int u, v, w;
for (int i = 0; i < edge_num; i++)
{
cin >> u >> v >> w;
matrix[u][v] = w;
}
if (SPFA())
Print();
else
cout << "Sorry,it have negative circle!\n";
return 0;
}运行如下：
**如果某个点进入队列的次数大于等于n，则存在负权回路。**为什么偏偏是n？
对于一个不存在负权回路的图，设其顶点数为n，我们把图稍微“转换”下，如下图A：
- 与源点0邻接的点{ 1, 2, 3 }作为第一批次；
- 与第一批次邻接的点{ 4, 5, 6, 7, 8, 9 }作为第二批次；
- ......
- 与第k-1批次邻接的点{ ...... }作为第k批次。
其中k≤n-1，当k=n-1时，即为上图B。
**每操作完一个批次的点，至少有一个点的最短路径被确定。 **这里读者只需从Dijkstra算法方面来考虑即可。Dijkstra每次循环都找出dist[]里的最小值，可以对应到这里的每个批次。
**一个不存在负权回路的图，最多有n-1个批次，每做完一个批次至少有一个点的最短路径被确定，即一个点的入队次数不超过n-1。**因为若一个顶点要入队列，则必存在一条权值之和更小的路径，而在最多做完n-1个批次后，所有顶点的最短路径都被确定。（这里需要注意的是，如果一个批次中，有多条路径对某顶点进行更新，则该顶点只会被入队一次，这从代码就可以看出）
一个点入队n-1次是什么样的呢？见下图：
n个顶点，源点为0，其中：
- 0到1，1到2，2到3，，，n-3到n-2的权值都为1；
- 0到i的权值为1；
- 1到i，2到i，3到i，，，n-2到i的权值从-1开始依次变小。
顶点i依次从0，1，2，3，，，n-2更新，共计n-1次，即入队n-1次。
对于一个不存在负权回路的图，我们假设其顶点数为n，边数为m。
引自SPFA论文：考虑一个随机图，运用均摊分析的思想，每个点的平均出度为$O(\frac m n)$，而每个点的平均入队次数为2，因此时间复杂度为$O(n⋅\frac m n⋅2)=O(2m)=O(m)$。
关于上述的“平均入队次数为2”，2这个数字从何得来，我也找不到证明，从网上各位朋友对此的一致态度：尚待商榷。但是可以确定的是，SPFA算法在随机图中的平均性能是优于Bellman_Ford算法的。
接着再看下SPFA的最差时间复杂度，它发生在一个完全图中，如下图：（参考自 xiazdong）
为了突出重点，故其余边未画出。我们约定：
- 从0分别到2，3，，，，n-2，n-1的边（即上半部分的曲线），满足0先更新k，待0更新完k-1后，k-1还可以更新k。
那么我们得出： 0点，入队1次，出度n-1次； 1点，入队1次，出度n-1次； 2点，入队2次，出度n-1次； 3点，入队3次，出度n-1次； . . . n-2点，入队n-2次，出度n-1次； n-1点，入队n-1次，出度n-1次；
因此时间复杂度为：$(n-1)⋅(1+1+2+3+...+(n-2)+(n-1))$，整理为$O(n^3)$，由于是完全图，也可以表达成$O(nm)$。
关于单源最短路径的算法：Dijkstra，Bellman_Ford，SPFA，讲到这里就全部结束了。但关于它们的适用点，彼此的联系以及由网上散出的一些错误概念，我觉得还需要进一步讲下，请看本系列的第四篇。