APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

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

2018年8月3日 2579点热度 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));
			}
		}
	}
}

 

标签: C++ Dijkstra logn 最短路 模板 洛谷 算法 落谷
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
寿屋:まちカドまぞく シャドウミストレス優子 Linux下网易云音乐只能sudo启动/无法启动解决 #动画#《中二病也要谈恋爱!第一季》观后感 #动漫#刀剑神域第二季1-25 1080P 我没有经验,还真是抱歉呢 关于P站(Pixiv)的搜索姿势
标签聚合
C/C++ ST 动漫 日常 HTML OI C++ 洛谷
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang