ACM

Dijkstra入门到精通(

(Dijkstra)是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。

百度百科

在图论的学习中我们常常会遇到这样一类问题:在一个给定的图中求某一个点到另一个点/其他所有点的最短路径的长度。

我们称这样的问题为单源最短路径问题

根据图的形式不同,我们用不同的算法解决这个问题。如果图中没有负边权,我们使用Dijkstra算法,否则使用SPFA算法。

Dijkstra算法的本质是动态规划,当然这个说法可能会引起争议,有的朋友也许会认为该算法的本质是贪心。我的理解是:贪心是基于局部最优解,而Dijkstra明显是从全局最优解来考虑的,并且能够列出边界条件与递推式,符合动态规划的特点。因此我坚持Dijkstra算法的本质是动态规划。

Dijkstra算法处理问题的核心思想是这样的:每次选择一个未被选择过的最近点,用它做中转点,更新出发点到其他点的最短距离。循环做n-1次以后所有的点到出发点的距离即为最短距离。

算法流程可以这样表示:

(选取n-1次){
	选择没有被选择过的最近点x 
	(枚举x所直连的点y)
		if (起始点s到y的当前距离>s到x的距离+x到y的边的长度)
			起始点s到y的当前距离=s到x的距离+x到y的边的长度
}

我们把起始点s到每一个点的当前距离用数组d来存储。初始化d数组赋一个极大值,d[s]赋为0。跑完该算法后,d数组就存储了出发点s到每一个点的最短距离。

下面给出一道例题:HDU2544

我的代码如下:

#include<bits/stdc++.h>
using namespace std;
#define N 101
#define M 20001
int hd[N],nx[M],e[M],w[M],d[N];
bool v[N];
int n,m;
void init(){
	memset(hd,0,sizeof(hd));
	memset(d,63,sizeof(d));
	int x,y,z,num=0;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		nx[++num]=hd[x],hd[x]=num,e[num]=y,w[num]=z;
		nx[++num]=hd[y],hd[y]=num,e[num]=x,w[num]=z;
	}
}
void Dijkstra(int s){
	memset(v,0,sizeof(v));
	d[s]=0,v[s]=true;
	for (int k=1;k<n;k++){
		for (int i=hd[s];i;i=nx[i])
			if (!v[e[i]]&&d[e[i]]>d[s]+w[i]) d[e[i]]=d[s]+w[i];
		int add=0;
		for (int i=1;i<=n;i++)
			if (!v[i]&&d[i]<d[add]) add=i;
		s=add,v[s]=true;
	}
}
void print(){
	printf("%d\n",d[n]);
}
int main(){
	while (true){
		init();
		if (n==0&&m==0) break;
		Dijkstra(1);
		print();
	}
	return 0;
}

Dijkstra算法的优化

仔细观察上面的代码,我们发现他的时间复杂度是O(n^2)的,面对动辄数十万的数据,这样的时间复杂度是不能接受的,因此我们需要对该算法进行优化,这里介绍最简单易懂的一种:优先队列优化Dijkstra(堆优化

因为使用了STL,所以我们不需要自己写一个堆了。直接使用priority_queue可以大大节省代码时间。

我们可以发现求最值的时间复杂度是O(n)的,而且这个操作我们还要执行n-1次。这是导致该算法时间复杂度高的根本原因。而我们知道,最值实际上并不需要每次都O(n)查询,而只需要维护一个堆即可。

我们把未被选取过的点的信息存入堆中,按照距离为关键字维护,这样我们虽然提高了更新距离的时间复杂度,但是查询最值的时间复杂度却降为O(logn)。

这样一来总时间复杂度为降为O(mlogn),代码如下:

#include<bits/stdc++.h>
using namespace std;
#define N 101
#define M 20001
#define Pii pair<int,int>
int hd[N],nx[M],e[M],w[M],d[N];
int n,m;
void init(){
	memset(hd,0,sizeof(hd));
	memset(d,63,sizeof(d));
	int x,y,z,num=0;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		nx[++num]=hd[x],hd[x]=num,e[num]=y,w[num]=z;
		nx[++num]=hd[y],hd[y]=num,e[num]=x,w[num]=z;
	}
}
void Dijkstra(int s){
	priority_queue<Pii,vector<Pii>,greater<Pii> > que;
	que.push(make_pair(0,s));d[s]=0;
	while (!que.empty()){
		Pii t=que.top();que.pop();
		if (t.first>d[t.second]) continue;
		for (int i=hd[t.second];i;i=nx[i])
			if (d[e[i]]>d[t.second]+w[i]){
				d[e[i]]=d[t.second]+w[i];
				que.push(make_pair(d[e[i]],e[i]));
			}
	}
}
void print(){
	printf("%d\n",d[n]);
}
int main(){
	while (true){
		init();
		if (n==0&&m==0) break;
		Dijkstra(1);
		print();
	}
	return 0;
}

当然这并非最优时间复杂度,配对堆优化可以进一步优化时间复杂度。但是代码量较大,在比赛中最广泛使用的仍然是本文所使用的方法。有兴趣的同学可以去了解一下其他优化方法,本文不作更深的讨论。

发表评论

电子邮件地址不会被公开。 必填项已用*标注