APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年8月3日 4185点热度 0人点赞 0条评论

简介

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));
			}
		}
	}
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ Dijkstra logn 最短路 模板 洛谷 算法 落谷
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
Lighttpd:配置SSL并强制跳转https配置 本博客黑白一周以悼念京都动画及遇难者 中国银行:天依小柠檬联名借记IC卡 #C/C++#数据结构:一维树状数组/二维树状数组模板 Manjaro 17.1.0+版本双系统安装后无引导的解决方法 #C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵)
标签聚合
洛谷 HTML C++ 日常 动漫 ST OI C/C++
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang