最短路篇

Floyd、SPFA and Dijkstra

松弛操作

最短路核心操作，可以理解成三角形的三边关系的翻版。（两边之和大于第三边->取两边之和和第三边的最小值）

Floyd 多源最短路

时间复杂度：$O(n^3)$

使用邻接矩阵，枚举中转点和两个点，更新这两个点之间的最短距离：$min(dis_{x-y},dis_{x-k}+dis_{k-y})$

代码过于简单不放了awa

SPFA 它死了（考场慎用）

时间复杂度：最差$O(nm)$

会被卡死。（有谷民甚至卡到200s）

真正用SPFA来解决最短路的很少，主要来处理有负权，判断正负环，差分约束。

使用桟或队列实现。（在有负环的情况下，栈比队列更快，但是如果没有负环的一般情况下，队列更快。）

桟实现SPFA

这和dfs有什么区别awa

代码如下：

void spfa(int u){
	vis[u]=1;
	for(int e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(dis[v]>dis[u]+sum[e]){
			dis[v]=dis[u]+sum[e];
			if(!vis[v])spfa(v);
		}
	}
	vis[u]=0;
}

队列实现SPFA

先把源点进队，然后用源点扩展更新，能迭代的都进队……
就是用队列里的点去迭代其他点，被迭代的点再次进队。

代码如下：

void SPFA(){
	for(int i=1;i<=m;i++)
		dis[i]=2147483647;
	dis[t]=0;
	Q.push(t);
	vis[t]=1;
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nex){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].len){
				dis[v]=dis[u]+e[i].len;
				if(!vis[v]){
					Q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}

SPFA拓展

判断负环

朴素做法：直接桟实现SPFA判断是否有重复松弛即可。

优化想法：

我们只需要找到权值和为负的回路，那不妨使距离数组 $dis$ 初始化为 $0$。
这样处理后，第一次拓展只会拓展到与起点相连边权为负的边。
那么我们就分别枚举所有的点作为起点，如果已经找到一个负环就不再继续枚举。
根据SPFA，我们找到的负环一定包含当前枚举的这个点。

差分约束

不讲awa

Dijkstra 不会被卡，但不能处理负权值。

使用 $dis$ 表示源点到每个点的最短距离。（初始为无限大，自己到自己为0）

每次找一个 $dis$ 值最小的没用过的点 $x$,遍历 $x$ 的所有出边进行松弛操作即可。

因此可以用堆优化到 $O(n log n)$。

代码如下：

void dij(int x){
	for(int i=1;i<=n;i++)
		dis[i]=(i==x)?0:1e9;
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int e=head[u];e;e=nxt[e]){
			int v=to[e];
			if(dis[v]>dis[u]+sum[e]){
				dis[v]=dis[u]+sum[e];
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}