堆優化的Dijkstra算法（鄰接表+優先隊列+pair）

【算法分析】

樸素的Dijkstra算法會逾時，是以必然需要進行優化。

對Dijkstra算法常見的優化方法有堆優化。而堆是一種優先隊列（priority_queue），故堆優化即基于優先隊列的優化。

【程式代碼】

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int MAXN=1000+7;
int n,m,x;

struct Edge {
	int to;
	int cost;
};
typedef pair<int, int> Pair;  // first是起點到其他頂點的最短距離, second頂點的編号

vector<Edge> G[MAXN];
int dis[MAXN];

void dijkstra(int st) {
	priority_queue<Pair, vector<Pair>, greater<Pair> > que;	//堆按照first從小到大的順序取值
	memset(dis, 0x3f, sizeof(dis));
	dis[st]=0;
	que.push(Pair(0,st));	// 把起點放入隊列

	while(!que.empty()) {
		Pair p=que.top();
		que.pop();
		int v=p.second;
		if(dis[v]<p.first)
			continue;
		for(int i=0; i<G[v].size(); i++) {
			Edge e=G[v][i];
			if(dis[e.to]>dis[v]+e.cost) {
				dis[e.to]=dis[v]+e.cost;
				que.push(Pair(dis[e.to],e.to));
			}
		}
	}

}

int main() {
	cin>>n>>m; //n:頂點數，m:邊數
	for(int i=1; i<=m; i++) {
		Edge e;
		cin>>x>>e.to>>e.cost;
		G[x].push_back(e);
	}

	dijkstra(1);

	for(int i=1; i<=n; i++) {
		cout<<dis[i]<<" ";
	}

	return 0;
}

/*
input:
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

output:
0 1 8 4 13 17
*/
           

【參考文獻】

https://blog.csdn.net/hpu2022/article/details/88597073

https://blog.csdn.net/heroacool/article/details/51014824

https://user.qzone.qq.com/3076688630/blog/1565248435

https://www.cnblogs.com/fusiwei/p/11390537.html