再述 Dijkstra

再述 Dijkstra

学 Dijkstra 好久了，今天再学了一遍，感觉推翻了好多自己的知识……

定义

一种用于求非负权值的图的单源最短路径的算法。

方法

已知：如果要求从起始点 s 到某一个点 x 的最短路径，显然只能从某一个已确认为最短路径的点转移。

给个图：

假设我们的起始点是点 1，现在我们用数组记录从原点到所有点的最短路径：

由于其他点的最短路未知，故先用 $\infty$ 代替，代码中用很大的一个数字代替即可。

注意到，我们由于要求出某个点出发，所有点的最短路，显然需要更新 $n$ 次，其中 $n$ 为顶点数量。

在这 $n$ 次循环中，我们可以处理出由若干顶点组成的已知最短路集合，称之为 $K$。

在每次循环中，用 $O(n)$ 可以找到距离 $u(u\in K)$ 最近的那个点，更新其最短路表格，并将其加入 $K$​ 中。

最后得到的结果：

证明

如何证明这种算法是对的？

假设我们有一张图：

从 $a$ 出发，求到 $e$ 的最短路径。其中 $a\to b\to e$ 这条路径已确认最短。

显然 $a\to c\to d$ 这条路径并不会比 $a\to b\to e$ 更优，且 $d\to e$ 这条边的权值一定非负（前提），所以 $a\to b\to e$ 这条路径一定是最优的。

算算时间复杂度，两层 $O(n)$ 的循环，就 $O(n^2)$，对于小数据可过。可允许大小约在 $n\le 10^4$。

优先队列优化

想想能否优化时间复杂度？

注意到，由于是要求 $n$ 个点的最短路，那么第一层的循环显然不能舍弃。

考虑优化时找到最近点的枚举步骤。

可以用一个优先队列存起来。存的东西：pair 类型，第一个元素是目前的最短路距离，第二个是点的编号。

那么众所周知，优先队列查找一个元素的时间复杂度是 $O(\log n)$ 的，其中 $n$ 为元素个数。

每次查找都是一个 $O(\log n)$，$n$ 次外循环，每次还要通过 $O(m)$ 的时间复杂度更新最短距离。

所以时间复杂度即为 $O((n+m)\log n)$。

一般来说，只要图是联通的，$m$ 基本都会比 $n$ 大，可近似为 $O(m\log n)$​。

局限性

但是，考虑到一种特殊的情况：完全图。

众所周知，完全图是一种 $m=n(n-1)$ 的特殊图，那么优先队列优化的时间复杂度就反而退化成了 $O(n^2\log n)$，反而不如朴素版。

代码

放下优先队列优化后的代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXM=5e5+5;
const int MAXN=1e4+5;
int n,m,s;
bool book[MAXN];
int dis[MAXN];
struct EDGE{
	int to,w,pre;
}edge[MAXM];
int head[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > heap;
void init()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=INT_MAX;
	}
	return;
}
void add(int from,int to,int w,int num)
{
	edge[num].to=to;
	edge[num].w=w;
	edge[num].pre=head[from];
	head[from]=num;
	return;
}
int u,v,w;
int main(){
	scanf("%d%d%d",&n,&m,&s);
	init();
	dis[s]=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w,i);
	}
	heap.push(make_pair(0,s));
	while(!heap.empty())
	{
		int t=heap.top().second;
		heap.pop();
		if(book[t]==true)
		{
			continue;
		}
		book[t]=true;
		for(int i=head[t];i!=0;i=edge[i].pre)
		{
			dis[edge[i].to]=min(dis[edge[i].to],dis[t]+edge[i].w);
			heap.push(make_pair(dis[edge[i].to],edge[i].to));
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	}
	puts("");
	return 0;
}