【Dijkstra】最短路算法的一種

首先，本文默認讀者基本熟悉Dijkstra基本原理

　　DIjkstra是單源最短路的一種算法。使用數組d[i]來儲存結點i到源點s的最短路徑長度，每次更新d[i]數組后，d[i]中最小的一定是一條最短路徑長度。也就是說每次更新后都能找到一條最短路徑，以下給出證明：

　　假設d[]數組中當前最小值對應的結點為u，那么d[u]<=d[i](u != i)假設d[u]不是結點u到源點s的最短路徑長度，那么一定有某種方式通過其他路徑到達u，使得d[v] + w < d[u]，但是由于通過源點到達其他結點的距離d[i] >= d[u] 那么不可能有其他更短的路徑到達u了，故d[u]就是最短路徑長度。重復以上過程n次，就能得到n個結點的最短路徑長度。

　　那么，具體應該怎么實現呢。

　　考慮到最小值查找，我們可以考慮幾種優化，比如優先隊列，可以降低時間復雜度，以下是個人實現代碼：

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 const int INF = 1e18 + 10,maxn = 1e5 + 10;
 5 
 6 bool vis[maxn];
 7 int d[maxn];
 8 struct node{
 9     int v,w;
10     
11     //重載運算符 < 這是一種方法
12     bool operator < (const node & x) const{
13         return w > x.w;
14     }
15 };
16 int n,m;
17 vector<node> G[maxn];
18 
19 void Dijkstra(int s){
20     fill(d,d + maxn,INF);
21     //將所有點斷開
22     d[s] = 0;
23     priority_queue<node> q;
24     
25     //確定最短路徑
26     //當前能確定的最短路
27     q.push({s,0});
28     while(!q.empty()){
29         node t = q.top();
30         q.pop();
31         int u = t.v;
32         if(vis[u]) continue;
33         vis[u] = true;
34         //相當于結點u已經確定最短路徑
35         
36         int len = G[u].size();
37         for(int i = 0; i < len; i++){
38             int v = G[u][i].v;
39             int w = G[u][i].w;
40             if(d[u] + w < d[v]){
41                 //這一步是收縮長度，找到沒有確定最短路徑的結點中的最小長度
42                 d[v] = d[u] + w;
43                 q.push({v,d[v]});
44             }
45         }
46     }
47     
48 }
49 signed main (){
50     ios::sync_with_stdio(false);
51     cin.tie(0),cout.tie(0);
52     
53     cin>>n>>m;
54     while(m--){
55         int u,v,w;
56         cin>>u>>v>>w;
57         G[u].push_back({v,w});
58     }
59     Dijkstra(1);
60     if(d[n] == INF){
61         cout<<-1<<'\n';
62     }else{
63         cout<<d[n]<<'\n';
64     }
65     return 0;
66 }

posted @ 2024-01-07 16:45 意外路過的番茄醬騎士閱讀(32) 評論(0) 收藏舉報

刷新頁面返回頂部

jiangjlon

【Dijkstra】最短路算法的一種

公告