【算法】单源最短路——SPFA

单源最短路除了dijkstra算法之外，还有一种常用的算法叫做SPFA（shortest path faster algorithm）算法，不同于dijkstra的复杂度为o(n^2)，SPFA算法的平均复杂度为o(kE)，E为边数，且k通常不超过2。

SPFA在实现时有bfs和dfs两种方式，但是在图的拓扑关系比较强时，用dfs会造成一条边的大量重复访问，会降低算法的稳定性，所以一般推荐使用bfs的方式。

SPFA是一种广义的bfs算法，同样适用队列实现的，但是每一个点可以入队的次数不超过n（图中点的总数）。

SPFA的核心思想如下：

最开始起点入队，然后考虑和起点相邻的点，更新dis数组，并将这些点入队；

当队列不为空时，每次取队首一个点，对这个点相邻的点进行松弛操作，即比较原先的dis和经过新加入的点的优化后的dis，如果松弛成功，且被松弛的点不在队列中，则将其加入队列，重复上述动作。

SPFA可以用来判断负环，我们开一个cnt数组记录每个点入队的次数，如果次数超过n说明出现负环。

代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 100;
int head[maxn], dis[maxn], vis[maxn], cnt[maxn], no, flag,m;
queue<int> q;
struct node
{
	int from;                 //起点
	int to;                   //终点
	int w;                    //权值
	int next;                 //下一条边的编号
}e[maxn];

void init()
{
	memset(head, -1, sizeof(head));      //将-1作为终结
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	memset(cnt, 0, sizeof(cnt));
	no = 0;
	flag = 1;
	while (!q.empty())
		q.pop();
}

void add(int u, int v, int w)
{
	e[no].from = u;
	e[no].to = v;
	e[no].w = w;
	e[no].next = head[u];           //将本条边的next值指向该起点之前记录的最后一条边
	head[u] = no++;                 //将该起点的最后一条边变为本边，并对编号no自加以便下一次使用
}
//邻接表

void SPFA_BFS(int u)
{
	vis[u] = 1;
	cnt[u] = 1;
	q.push(u);                      //顶点入队，且统计顶点入队次数

	while (!q.empty())
	{
		int temp = q.front();
		q.pop();                    //队列非空，则将队首元素读入并令其出队
		vis[temp] = 0;              //消除标记
		for (int i = head[temp]; i != -1; i = e[i].next)
		{
			int to = e[i].to;
			int w = e[i].w;
			if (dis[to] > dis[temp] +w)
			{
				dis[to] = dis[temp] + w;
				if (!vis[to])
				{
					vis[to] = 1;
					q.push(to);
					cnt[to]++;
					if (cnt[to] > m)
						flag = -1; //超过n次有负边
				}
			}
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	int u, v, w, n;                         //n是边数
	scanf("%d%d",&m, &n);
	init();
	while (n--)
	{
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
		add(v, u, w);                       //如果是无向图一定要录两遍
	}

	int target;
	scanf("%d", &target);
	dis[target] = 0;
	SPFA_BFS(target);
	for (int i = 1; i <= m; i++)
	{
		printf("%d : %d\n", i, dis[i]);
	}

	return 0;
}