SPFA详解（^-^)_牛客博客

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环

如果没必要判负环建议使用Dijkstra

SPFA判断负环：如果一个点进入队列达到n次，则表明图中存在负环，没有最短路径。

因为有负权，所以每次松弛操作都能更新最小值，就一直循环操作下去

主要思想及方法：

设一个数组用来存储源点到其他顶点的最短路径，初始化时，其他顶点为无穷。

再设立一个队列，读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队

以此循环，直到队空为止就完成了单源最短路的求解

转大神的样例：

首先建立起始点a到其余各点的
最短路径表格

首先源点a入队，当队列非空时：
　１、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：

在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点
需要入队，此时，队列中新入队了三个结点b,c,d

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：

在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要
入队，此时队列中的元素为c，d，e

队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：

在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此
e不用入队了，f要入队，此时队列中的元素为d，e，f

队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g

队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：

在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e

队首元素***出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：

在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b
队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：

在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了

最终a到g的最短路径为１４

下面详细代码：

#include <stdio.h>
#include <iostream>
#include<vector> 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+10;
struct edge{
	int to; // 当前点的下一顶点 
	int cost;//两点之间的权值 
};

vector <edge> adjmap[maxn];

int dis[maxn];//存储最短路径
int vis[maxn];//标记该顶点是否在队列里 
int path[maxn];
int inque[maxn]; //统计次数 
int N,M; // N个点 ,M条边  
bool SPFA(int s , int totalnode)
{
	for(int i = 0 ; i <= N ; i++)
	{
		dis[i] = INF;
	}
	queue<int> q;
	dis[s] = 0;//初始数组 
	
	q.push(s);//最初队列里的顶点
	inque[s] = 1;// 统计入队次数
	
	while(!q.empty())
	{
		int u = q.front();//取首
		q.pop();
		vis[u] = 0;//消除标记 
		//遍历顶点u邻接表
		for(int v = 0 ; v < adjmap[u].size() ; v++)
		{
			int to = adjmap[u][v].to;//下一顶点 
			if(dis[u]+adjmap[u][v].cost < dis[to])//松弛操作 
			{
				dis[to] = dis[u]+adjmap[u][v].cost;
				if(!vis[to]) {
                    //定点to不在队列内
                    vis[to] = 1;//标记
                    inque[to]++;//统计次数
                    q.push(to);//入队
                    if(inque[to]>totalnode) {
                        //超过如对次数上限 说明有负数环
                        return false;
                    	}
			 	} 
		 	} 
	 	}
	}
	 return true; 
}
int main()
{
	
	int u,v,cost; //从u -> v 有一条花费为cost的边 
	cin>>N>>M;
	for(int i = 0 ; i < M ; i++)
	{
		scanf("%d%d%d",&u,&v,&cost);
		edge te ;
		te.to = v;
		te.cost = cost;
		adjmap[u].push_back(te);
	}
	SPFA(1,N);
	for(int i = 2 ; i <= N ; i++)
	{
		printf("%d ",dis[i]);
	}
}
/*
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

*/