【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 }

 

热门相关:重生真的很淡定   我有一张均富卡   完美的性爱味道   密愛   我同学的妈妈