C/C++ 最短路算法Dijkstra算法 + 堆优化模板

简介

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

无优化复杂度：O(n ^ 2)

那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？

因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。

洛谷：P3371（弱化版） Spfa能过    P4779（标准版）卡Spfa

普通算法

这是Dijkstra的普通算法（无优化）复杂度O（n ^ 2）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;


static const int MAXN = 100005;
static const int MAXM = 200005;
static const int INF = 2147483647;


struct node {
	int dis;
	int next;
	int to;
} e[MAXM];

int head[MAXN],cnt,n,m,s;
int dis[MAXN];
bool vis[MAXN];

void add(int ,int ,int );
void Init();
void Dijkstra();

int main() {
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1;i <= m;++i) {
		int from,to,dis;
		scanf("%d%d%d",&from,&to,&dis);
		add(from,to,dis);
	}
	Dijkstra();
	for(int i = 1;i <= n;++i) printf("%d ",dis[i]);
	return 0;
}

void add(int from,int to,int dis) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	e[cnt].dis = dis;
	head[from] = cnt;
}

void Init() {
	for(int i = 1;i <= n;++i) dis[i] = (i == s ? 0 : INF);
}

void Dijkstra() {
	Init();
	for(int i = 1;i <= n;++i) {
		int flag = 214748364,t = -1;
		for(int j = 1;j <= n;++j)
			if(!vis[j] && dis[j] < flag) {
				flag = dis[j];
				t = j;
			}
		if(t == -1) break;
		vis[t] = true;
		for(int j = head[t];j;j = e[j].next) if(!vis[e[j].to]) dis[e[j].to] = min(dis[e[j].to],dis[t] + e[j].dis);
	}
}

堆优化

这是Dijkstra算法的堆优化。复杂度为O（nlogn）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;


static const int MAXN = 100005;
static const int MAXM = 200005;
static const int INF = 2147483647;


struct node {
	int dis;
	int next;
	int to;
} e[MAXM];

int head[MAXN],cnt,n,m,s;
int dis[MAXN];
bool vis[MAXN];

void add(int ,int ,int );
void Init();
void Dijkstra_Heap();

int main() {
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1;i <= m;++i) {
		int from,to,dis;
		scanf("%d%d%d",&from,&to,&dis);
		add(from,to,dis);
	}
	Dijkstra_Heap();
	for(int i = 1;i <= n;++i) printf("%d ",dis[i]);
	return 0;
}

void add(int from,int to,int dis) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	e[cnt].dis = dis;
	head[from] = cnt;
}

void Init() {
	for(int i = 1;i <= n;++i) dis[i] = (i == s ? 0 : INF);
}

void Dijkstra_Heap() {
	priority_queue <pair <int ,int > ,vector <pair <int ,int > >,greater <pair <int ,int > > > Q;
	Init();
	Q.push(make_pair(0,s));
	while(!Q.empty()) {
		int u = Q.top().second;
		Q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = head[u];i;i = e[i].next) {
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].dis) {
				dis[v] = dis[u] + e[i].dis;
				if(!vis[v]) Q.push(make_pair(dis[v],v));
			}
		}
	}
}