代码随想录算法训练营Day59 图论09 | Dijkstra（堆优化版）精讲、Bellman_ford 算法精讲

Dijkstra（堆优化版）精讲

还是非负权变最短路问题，堆优化是降低原始复杂度的一种写法，把每次寻找最小值的遍历操作改为使用小顶堆，每次取顶值元素就可实现寻找最小值的操作。

和朴素版的区别：

朴素版：遍历每个节点（n次，每次敲定一个节点的最短距离）-内循环再遍历n次，因为要比较所有节点的minDist的最小值-把最小cur标记为访问过-遍历所有节点看谁与cur连接并且经过cur之后到该节点的距离更短从而更新

堆优化版：把起点的{距离，节点}放入小顶堆 - while循环，只要堆不为空，就一直取顶弹出，判断是否访问过，如果访问过就continue，没访问过就标记访问，然后遍历graph[cur]所连接的各个节点，符合条件就更新，更新后再放入堆

注：堆优化版可以把同一节点编号但不同距离的pair放入堆中，因为大距离的pair会晚于小距离的pair被取到，然后标记访问过，之后再轮到大距离的pair时就直接continue了。

#include<iostream> using namespace std; #include<climits> #include<vector> #include<queue> int main(){ int n,m,s,t,val; cin>>n>>m; vector<vector<pair<int,int>>> graph(n+1); while(m--){ cin>>s>>t>>val; graph[s].push_back({t,val}); } vector<int> minDist(n+1,INT_MAX); vector<bool> visited(n+1,false); int start = 1; int end = n; minDist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0,start}); while(!pq.empty()){ int curDist = pq.top().first; int cur = pq.top().second; pq.pop(); if(visited[cur]) continue; visited[cur] = true; //开始更新距离 for(auto& edge:graph[cur]){ int note = edge.first; int Dist = edge.second; if(!visited[note] && minDist[cur]+Dist<minDist[note]){ minDist[note] = minDist[cur]+Dist; pq.push({minDist[note],note}); } } } if(minDist[end]==INT_MAX) cout<<-1<<endl; else cout<<minDist[end]<<endl; }

Bellman_ford 算法精讲

bellman算法是应对最短路径问题中负权边但没有负权环的情况的。它也可以应对非负权边的最短路问题，只是效率没有dijkstra高。

思路：对每条边松弛n-1次，松弛的意思就是如果通过from到to这条边到to会让to的距离变小，就把minDist[to]更新为minDist[from]+val(from->to)

原因：每松弛一次，就会让所有已经有有效距离的节点向外走一步，所以松弛n-1次就会遍历完所有从起点到终点的路径，又由于每到一个节点都会经过路径更新，距离更小就更新，距离更大保持不变，所以最后留下的一定就是最小的节点到起点的距离了。

#include<iostream> using namespace std; #include<vector> #include<climits> int main(){ int n,m,s,t,val; cin>>n>>m; vector<vector<int>> graph; while(m--){ cin>>s>>t>>val; graph.push_back({s,t,val}); } vector<int> minDist(n+1,INT_MAX); minDist[1] = 0; for(int i=1;i<n;i++){ for(auto &edge:graph){ int from = edge[0]; int to = edge[1]; int price = edge[2]; if(minDist[from]!=INT_MAX && minDist[to]>minDist[from]+price){ minDist[to] = minDist[from]+price; } } } if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl; else cout<<minDist[n]<<endl; }