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