dijkstra 复杂度证明

我们用以下代码为例分析复杂度

#include<bits/stdc++.h>
#include<climits>
#define fir first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
inline int read() {
	int x=0,f=1; char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int N=1e5+50,M=2e5+50;
int head[N],nxt[M],to[M],W[M],num;
ll dis[N];
void add(int u,int v,int w) {
	++num;nxt[num]=head[u];to[num]=v;W[num]=w;head[u]=num;
}
priority_queue<PII,vector<PII>,greater<PII> >q;
int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read(),m=read(),s=read();
	for(int i=1;i<=m;i++) {
		int u=read(),v=read(),w=read();
		add(u,v,w);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({dis[s],s});
	while(!q.empty()) {
		int u=q.top().se; 
		if(dis[u]!=q.top().fir) {//写法较奇怪，此处如果dis[u]!=q.top().fir，则dis[u]<q.top().fir，此时{dis[u],u}已经出队列一次，因此此时不需要使用u节点更新
			q.pop();
			continue;
		}q.pop();
		for(int i=head[u];i;i=nxt[i]) {
			int v=to[i];
			if(dis[v]>dis[u]+W[i]) {
				dis[v]=dis[u]+W[i];
				q.push({dis[v],v});
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
	return 0;
}

dijkstra 实际复杂度为 \(\text{O}(m\log n)\)

每个点只会被更新一次，每条边只会更新其他点一次，因此复杂度为 \(\text{O}(m\log n^2)=\text{O}(2m\log n)\)，所以复杂度为 \(\text{O}(m\log n)\)。

by lyk&yjx