图论初步——最短路(2)

Dijkstra算法优化

关于Dijkstra

详见图论初步——最短路(1)
前面的文章中，我们提到了$Dijkstra$算法的核心就是每次找到剩余的点中的最小值。
这一步用了一个$for$循环，很花时间。
所以如何快速找到剩下的点的最小值，就是我们要解决的问题。

方法1：线段树

每次找到最小值及其编号，然后赋为极大值，以不影响后面取最小值。
时间复杂度：$O(logn)$单次，$O(nlogn)$建树，总复杂度$O(nlogn)$
代码复杂度：难

方法2：分块

操作方法同线段树
时间复杂度：单次$O(\sqrt{n})$,总复杂度$O(n\sqrt{n})$
代码复杂度：中

方法3：堆

建立小根堆，找到最小值后弹出堆，更新距离时在堆里修改。
时间复杂度：单次操作$O(logn)$，总复杂度$O(nlogn)$
代码复杂度：中

方法3.5：优先队列

从方法3得到提示，我们可以用$STL$里面的priority_queue，即优先队列
时间复杂度：同堆
代码复杂度：简单

优先队列实现方式

由于要同时记录距离及编号，所以我们考虑使用$STL$中的make_pair函数。在优先队列中自动按第一关键字排序。

细节

由于c++优先队列默认为大根堆，而我们需要小根堆，故有2种操作方式：
第一种(不要轻易尝试)：

#define pair<int,int> pii
priority_queue<pii,vector<pii>,greater<pii> >;

第二种：插入时插入负数，因为我们只需要点的具体编号，距离只做比较用。

代码

#include<bits/stdc++.h>
using namespace std;
int first[200005],Next[200005],to[200005],w[200005],tot=0,d[200005];
bool vis[200005];
int Read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')  f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void Print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)  Print(x/10);
	putchar(x%10+'0');
}
void add(int x,int y,int z){
	Next[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
priority_queue< pair<int,int> > q;
void dijkstra(int x){
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(vis,false,sizeof(vis));
	d[x]=0;
	pair<int,int> p=make_pair(0,x);
	q.push(p);
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])  continue;
		vis[u]=true;
		int e,v;
		for(e=first[u];e,v=to[e];e=Next[e]){
			if(d[v]>d[u]+w[e]){
				d[v]=d[u]+w[e];
				q.push(make_pair(-d[v],v));
			}
		}
	}
}
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,z;
		x=Read();
		y=Read();
		z=Read();
		add(x,y,z);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		Print(d[i]);
		putchar(' ');
	}
}

spfa算法

缺点：容易被卡，但随机数据时很快
优点：可以处理负权情况
与$Dijkstra$一个点标记后无法被再次更新相比，$spfa$允许一个点多次被更新，这使它可以处理有负权的情况，与$Dijkstra$优先队列不同，$spfa$使用普通队列。

实现

先将起点放入队列，然后只要队列不空，就取出队首，用它来更新其余点，如果成功更新，就判断该点是否在队列里，如果不是，则让其入队，这样一直下去，直到队列为空。

拓展

当存在负环时，就不存在最短路了，这时spfa就会展现出其优点。在存在最短路的情况下，一个点最多被其余的点更新一次，也就是更新$n-1$次。所以记录该点入队的次数，如果达到$n$次，就存在负环，跳出$spfa$过程。

代码

spfa：

void spfa()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		d[i]=2147483647;
		inq[i]=false;
	}
	q.push(s);
	inq[s]=true;
	d[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=head[u];i;i=next[i])
		{
			int v=to[i];
			if(d[v]>d[u]+dis[i])
			{
				d[v]=d[u]+dis[i];
				if(!inq[v])
				{
					q.push(v);
					inq[v]=true;
				}
			}
		}
	}
}

负环：

bool spfa(int s)
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		d[i]=2147483647;
		inq[i]=false;
		cnt[i]=0;
	}
	q.push(s);
	inq[s]=true;
	d[s]=0;
	cnt[s]++;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=head[u];i;i=next[i])
		{
			int v=to[i];
			if(d[v]>d[u]+dis[i])
			{
				d[v]=d[u]+dis[i];
				if(!inq[v])
				{
					q.push(v);
					inq[v]=true;
					cnt[v]++;
					if(cnt[v]>n)  return false;
				}
			}
		}
	}
	return true;
}

顺便一提，想为一个数组赋特定值时可以使用fill函数，例如将$a[1]-a[n]$赋为100000，可以

fill(a+1,a+n+1,100000);

练习题
dijkstra 洛谷P4779
spfa 洛谷P3371
负环 洛谷P3385