Dijkstra求最短路（樸素and堆優化）

題目來自ACWING

題目描述：

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出1号點到n号點的最短距離，如果無法從1号點走到n号點，則輸出-1。

輸入格式

第一行包含整數n和m。

接下來m行每行包含三個整數x，y，z，表示點x和點y之間存在一條有向邊，邊長為z。

輸出格式

輸出一個整數，表示1号點到n号點的最短距離。

如果路徑不存在，則輸出-1。

資料範圍

1≤n≤500,

1≤m≤10^5,

圖中涉及邊長均不超過10000。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4
           

輸出樣例：

3

時間複雜度：

Dijkstra: O（N^2）；

題目分析：

樸素Dijkstra的方法很直覺，每次周遊下所有的邊，找到點集外可加入點集的距離最小的點，加入到點集（點集中的點應確定是距離最短的）。再嘗試更新下新加入的點附近的點的距離。每次執行下找最短邊的操作時間複雜度是O(n)，最壞情況下終點在最後才會被加入到點集，是以過程會被重複n次，故樸素的dijkstra算法的時間複雜度為O（n^2)。

代碼如下：

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 510;
int n, m;
int g[maxn][maxn], d[maxn];
bool vis[maxn];
int Dijkstra() {
	memset(d, 0x3f, sizeof(d));
	d[1] = 0;
	for (int i = 0;i < n;i++) {
		int t = -1;
		for (int j = 1;j <= n;j++) {
			if (!vis[j] && (t == -1 || d[t] > d[j]))
				t = j;
			
		}
		vis[t] = true;
		for (int j = 1;j <= n;j++) {
			if (!vis[j] && d[t] +g[t][j] < d[j])
				d[j] = d[t] + g[t][j];
		}
	}
	if (d[n] == 0x3f)
		return -1;
	return d[n];
}

int main() {
	scanf_s("%d%d", &n, &m);
	int a, b, c;
	memset(g, 0x3f, sizeof(g));
	while (m--) {
		scanf_s("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);
	}
	cout << Dijkstra() << endl;
	return 0;
}

           

對于稀疏圖問題，樸素Dijkstra往往很難取得好結果，是以需要加以優化。我們利用優先隊列，實作堆優化的Dijkstra。

代碼如下

來自https://www.cnblogs.com/-Wind-/p/10164910.html

1 #include <cstdio>
 2 #include <queue>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int n,m,s;
 7 int head[100001],dis[100001],cnt;
 8 bool vis[100001];
 9 struct qwq{
10     int from,to,next;
11     long long len;
12 }edge[200001];
13 void add(int u,int v,int w)
14 {
15     cnt++;
16     edge[cnt].from=u;
17     edge[cnt].to=v;
18     edge[cnt].len=w;
19     edge[cnt].next=head[u];
20     head[u]=cnt;
21     return;
22 }
23 struct node{
24     int index,dist;
25     bool operator < (const node &x)const
26     {
27         return dist>x.dist;
28     }
29 };
30 priority_queue<node> q; 
31 int main()
32 {
33     scanf("%d%d%d",&n,&m,&s);
34     for(int i=1;i<=m;i++)
35     {
36         int u,v,w;
37         scanf("%d%d%d",&u,&v,&w);
38         add(u,v,w);
39     }
40     for(int i=1;i<=n;i++)
41     dis[i]=2147483647;
42     dis[s]=0;
43     q.push(node{s,0});
44     while(!q.empty())
45     {
46         node x=q.top();
47         q.pop();
48         int u=x.index;
49         if(vis[u]) continue;
50         vis[u]=1;
51         for(int i=head[u];i;i=edge[i].next)
52         {
53             if(dis[edge[i].to]>dis[u]+edge[i].len)
54             {
55                 dis[edge[i].to]=dis[u]+edge[i].len;
56                 q.push(node{edge[i].to,dis[edge[i].to]});
57             }
58         }
59     }
60     for(int i=1;i<=n;i++)
61     printf("%d ",dis[i]);
62     return 0;
63 }