算法简介

迪杰斯特拉(Dijkstra)算法是图论中的最短路算法，它可以实现求解特定起点到任一点的最短路径。对于顶点个数为$n$的图，如果需要求解每两个点之间的最短路径则需要跑$n$次迪杰斯特拉算法。

迪杰斯特拉的时间复杂度为$O(n^2)$，缺点是不适用于带负权边的图。

算法思想

迪杰斯特拉算法基于贪心的思想，不断地寻找中间结点$w$使得$u\to w\to v$的距离小于$u\to v$的距离，即用中间值更新结果。相似算法思想参考朴素迪杰斯特拉算法邻接矩阵法。

朴素迪杰斯特拉算法

邻接矩阵法

这是最简单的迪杰斯特拉算法，采用邻接矩阵存储，这里以邻接矩阵$map[i][j]$表示$i$到$j$的距离，顶点到自身距离$map[i][i]=0$，如果$i$到$j$没有边则$map[i][j]=\infty$。

对于一个顶点个数为$n$的图，若求点$x$到任一点的最短路径长度，迪杰斯特拉维护一个长度为$n$的数组$dist[]$，$dist[y]$表示$x$到$y$的最短路径长度。其次，还维护了一个长度为$n$的$visit[]$数组，$visit[j]$表示$j$是否被访问过。

1. 对于$dist$数组，首先初始化$dist[]$为$\infty$表示$x$到任一点距离无穷大，但是$dist[x]=0$表示$x$到自己距离为$0$，初始化$visit[]$数组值为$0$表示点未被访问，执行第$2$步。
2. 查找未被访问过的顶点中使得$dist[j]$最小的顶点$j$，并把$j$标记为已访问，即$visit[j]=1$，执行第$3$步。
3. 用$j$去更新路径，查看以$j$作为中间结点是否比已知路更短，更短则更新。$dist[y]=min(dist[y],dist[j]+map[j][y])$，回到第$2$步，直到所有顶点都被访问。

void Dijkstra(int x){//求x到任一点
	memset(dist,INF,sizeof(dist));//dist[]=INF
	dist[x]=0;
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=n;i++){
		int j=0;
		for(int k=1;k<=n;k++){//找最小未被访问的dist[j]
			if(!visit[k]&&dist[k]<=dist[j]){
				j=k;
			}
		}
		visit[j]=1;
		for(int k=1;k<=n;k++){//更新dist[j]
			dist[k]=min(dist[k],dist[j]+map[j][k]);
		}
	}
}

邻接表法

除了易于实现的邻接矩阵，迪杰斯特拉算法同样可以改写成邻接表形式。这里采取链式前向星结构，其实所谓的链式前向星，就是用数组模拟实现的链表，也就是静态链表。$head[]$数组表示顶点数组，指向与顶点连接的边的下标。$to[k]$数组表示第$k$条边的指向顶点编号，$val[k]$表示第$k$条边的权值。

void Dijkstra(int x){//求x到任一点
	memset(dist,INF,sizeof(dist));//dist[]=INF
	dist[x]=0;
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=n;i++){
		int j=0;
		for(int k=1;k<=n;k++){//找最小未被访问的dist[j]
			if(!visit[k]&&dist[k]<=dist[j]){
				j=k;
			}
		}
		visit[j]=1;
		for(int k=head[j];k;k=next[k]){//更新dist[j]
			dist[to[k]]=min(dist[to[k]],dist[j]+val[k]);
		}
	}
}

堆优化迪杰斯特拉算法

• 朴素迪杰斯特拉算法的可优化点在于查找未被访问过的满足最小$dist[j]$的顶点$j$，这个过程可以采取堆优化，也就是所谓的优先队列。

算法思想

优化查找过程，首先初始化堆只有源点，初始化$dist[]=INF$，除了$dist[x]=0$。然后每次从堆中取出最小距离的中间结点$j$并出堆，将所有能更新的$dist[j]+map[j][k]<dist[k]$的$dist[k]$更新为$dist[j]+map[j][k]$并将结点$k$入堆，重复此过程直到堆空为止。

提示

1. 由于朴素算法是用数组编号来映射结点的，而堆排序会打乱原映射顺序，所以我们考虑用$C++$自带的$pair<typeA,typeB>$来存储结点，由于$pair$默认按照$typeA$排序，所以$typeA$应该是距离，$typeB$是结点编号。
2. $c++$的$priority\_queue$默认是大顶堆，所以需要重载比较运算符。
3. $priority\_queue$位于$<queue>$，$pair$位于$<utility>$。

邻接矩阵法

void Dijkstra(int x){//求x到任一点
	memset(dist,INF,sizeof(dist));//初始化最远距离
	typedef pair<int,int> pr;//分别存储距离和顶点编号
	priority_queue<pr,vector<pr>,greater<pr> > Q;//优先队列,重载运算符
	dist[x]=0;//初始化源点自身距离为0
	Q.push(make_pair(0,x));
	while(!Q.empty()){
		int j=Q.top().second;
		Q.pop();
		if(visit[j]) continue;
		visit[j]=1;
		for(int k=1;k<=n;k++){//更新dist[j]
			if(dist[j]+map[j][k]<dist[k]){
				dist[k]=dist[j]+map[j][k];
				if(!visit[k]) Q.push(make_pair(dist[k],k));
			}
		}
	}
}

邻接表法

同样的，堆优化也可以采用链式前向星结构，详细数组含义参考朴素算法的邻接表法。

void Dijkstra(int x){//求x到任一点
	memset(dist,INF,sizeof(dist));//初始化最远距离
	typedef pair<int,int> pr;//分别存储距离和顶点编号
	priority_queue<pr,vector<pr>,greater<pr> > Q;//优先队列,重载运算符
	dist[x]=0;//初始化源点自身距离为0
	Q.push(make_pair(0,x));
	while(!Q.empty()){
		int j=Q.top().second;
		Q.pop();
		if(visit[j]) continue;
		visit[j]=1;
		for(int k=head[j];k;k=last[k]){//更新dist[j]
			if(dist[j]+val[k]<dist[to[k]]){
				dist[to[k]]=dist[j]+val[k];
				if(!visit[to[k]) Q.push(make_pair(dist[to[k]],to[k]));
			}
		}
	}
}

总结

迪杰斯特拉算法堆优化后效率很高，优于$SPFA$算法，但是不能用于带负权边的图，时间复杂度上堆优化效率高于朴素算法，空间复杂度上邻接表法优于邻接矩阵法。