原文衔接：http://blog.csdn.net/runninghui/article/details/8895586
解决存在负环的图的单源最短路径，bellman-ford算法是比较经典的一个，但是大家都知道，这个算法的效率并不咋的，因为它只知道要求单源最短路，至多做|v|（j图的结点数）次松弛操作，感觉有点盲目吧，这里介绍一个有西南交通大学段凡丁1994年发明的一个算法即SPFA，很大程度上优化了bellman-ford算法(建议没有学过的，先去了解一下这个算法)，算法的时间效率我就不说了，因为我觉得当我们熟悉某个算法之后，分析时间复杂度就没什么问题了，如果盲目的记忆，意义不大。
SPFA算法的精妙之处在于不是盲目的做松弛操作，而是用一个队列保存当前做了松弛操作的结点。只要队列不空，就可以继续从队列里面取点，做松弛操作，想想bellman-ford算法吧,它只知道做|v|次循环就对了。下面讲讲SPFA为什么这样做呢？还是举个例子：
当前源点1在队列里面，于是我们取了1结点来做对图进行松弛操作，显然这个时候2,3结点的距离更新了，入了队列，我们假设他们没入队列,即现在队列已经空了，那么还有没有必要继续做松弛操作呢？显然没必要了啊，因为源点1要到其他结点必须经过2或3结点啊。现在懂了吧。
先讲一下SPFA的大致思想
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，如果该点没有在队列中，则将其入队。 直到队列为空时算法结束。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）
SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。个人觉得LLL优化每次要求平均值，不太好，为了简单，我们可以之间用C++STL里面的优先队列来进行SLF优化
下面贴一下用用优先队列来进行SLF优化代码
- #include <iostream>
- #include <cstring>
- #include <queue>
- using namespace std;
- const int INF = 0x3fffffff;
- const int MAX = 100;
- int map[MAX][MAX];
- int dis[MAX];
- bool vis[MAX];
- int num[MAX];//记录每个结点入队的次数
- struct cmp
- {
- bool operator()(int x,int y)
- {
- return x>y;
- }
- };
- bool SPFA(int s0,int n)
- {
- priority_queue<int,vector<int>,cmp> q;
- memset(vis,false,sizeof(vis));
- memset(num,0,sizeof(num));
- for(int i=0;i<n;i++)
- dis[i] = INF;
- dis[s0] = 0;
- q.push(s0);
- vis[s0] = true;
- num[s0]++;
- while(!q.empty())
- {
- int p = q.top();
- q.pop();
- for(int i=0;i<n;i++)
- {
- if(dis[p]+map[p][i]<dis[i])
- {
- dis[i] = dis[p]+map[p][i];
- if(!vis[i])
- {
- q.push(i);
- num[i]++;
- if(num[i]>n)//存在负环
- {
- return false;
- }
- vis[i]=true;
- }
- }
- }
- vis[p] = false;
- }
- return true;
- }