SPFA算法

单源最短路算法，可以处理负边权，平均时间复杂度\(O(kn)\)，最坏时间复杂度\(O(mn)\)

问题描述：

有一个连通图\(G=(V,E)\)，连接节点\(i\)和节点\(j\)的边权写作\(e^i_j\)（\(e^i_j\geq 0\)），求从起点（\(s, s\in V\)）开始，到其它各个节点（\(d, d\in V-s\)）的最短路长度。

思路详解：

设从起点s到节点d的最短路用\(dis[d]\)表示，当然一开始除了\(dis[s]\)，都初始化为无穷大。
我们要做的事情就是在搜索整张图的时候，不断更新\(dis\)。
假设我们在BFS这张图，现在有从节点\(i\)到节点\(j\)的边\(e^i_j\)，那么\(dis[j]=min(dis[j], dis[i]+e^i_j)\)。
需要注意的是，如果\(dis[j]\)更新了，那么以\(j\)为起点的图连通分支的\(dis\)都是有可能要改变的。
所以需要把\(j\)节点重新放进BFS的队列中，以便尝试更新以\(j\)为起点的图连通分支的\(dis\)。这就是SPFA的核心思想！
如果图里面出现了负环，那么这个环上节点的\(dis\)就会不断地更新。
所以我们只需要对每个节点d定义一个计数器，用来统计从起点s到节点d这条路上\(dis\)的更新次数（也可以理解为s到d的最短路边数），如果更新次数大于n-1（一共n个点），那么可以断定有负环了。
当然还有一种效率较低的方法，那就是判断节点的入队次数，这里就不多介绍了。

SPFA和Dijkstra的一个显著区别是：SPFA会重复搜索一些节点，而Dijikstra的搜索过程没有重复。
Dijikstra贪心地每次取距离最小的节点进行更新，并且不会更新已经更新过的节点，要保证正确性就必须要求边权不为负。
SPFA则会更新已经更新过的节点，所以对边权没有要求，自然其时间复杂度也会更高。

模板题目参考：洛谷P3385

代码参考：

#include <bits/stdc++.h>

const int maxN = 100005, maxM = 500005;

struct Edge
{
	int to, dis, next;
}edge[maxM];

int head[maxN], cnt;

inline void add_edge(int u, int v, int d)
{
	cnt++;
	edge[cnt].dis = d;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

std::queue<int> nd;

int dis[maxN], cost[maxN];
bool vis[maxN];

bool spfa(int n)
{
	dis[1] = 0;
	nd.push(1);
	vis[1] = true;
	while (!nd.empty())
	{
		int tmp = nd.front();
		nd.pop();
		vis[tmp] = false;
		for (int i = head[tmp]; i; i = edge[i].next)
		{
			int y = edge[i].to;
			if (dis[tmp] + edge[i].dis < dis[y])
			{
				dis[y] = dis[tmp] + edge[i].dis;
				cost[y] = cost[tmp] + 1;
				if (cost[y] >= n)
					return false;
				if (!vis[y])
				{
					nd.push(y);
					vis[y] = true;
				}
			}
		}
	}
	return true;
}