【Dijkstra】最短路算法的一种-Toy模板网

这篇具有很好参考价值的文章主要介绍了【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 }