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

Dijkstra堆优化版精讲还是非负权变最短路问题堆优化是降低原始复杂度的一种写法把每次寻找最小值的遍历操作改为使用小顶堆每次取顶值元素就可实现寻找最小值的操作。和朴素版的区别朴素版遍历每个节点n次每次敲定一个节点的最短距离-内循环再遍历n次因为要比较所有节点的minDist的最小值-把最小cur标记为访问过-遍历所有节点看谁与cur连接并且经过cur之后到该节点的距离更短从而更新堆优化版把起点的{距离节点}放入小顶堆 - while循环只要堆不为空就一直取顶弹出判断是否访问过如果访问过就continue没访问过就标记访问然后遍历graph[cur]所连接的各个节点符合条件就更新更新后再放入堆注堆优化版可以把同一节点编号但不同距离的pair放入堆中因为大距离的pair会晚于小距离的pair被取到然后标记访问过之后再轮到大距离的pair时就直接continue了。#includeiostream using namespace std; #includeclimits #includevector #includequeue int main(){ int n,m,s,t,val; cinnm; vectorvectorpairint,int graph(n1); while(m--){ cinstval; graph[s].push_back({t,val}); } vectorint minDist(n1,INT_MAX); vectorbool visited(n1,false); int start 1; int end n; minDist[start] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,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]DistminDist[note]){ minDist[note] minDist[cur]Dist; pq.push({minDist[note],note}); } } } if(minDist[end]INT_MAX) cout-1endl; else coutminDist[end]endl; }Bellman_ford 算法精讲bellman算法是应对最短路径问题中负权边但没有负权环的情况的。它也可以应对非负权边的最短路问题只是效率没有dijkstra高。思路对每条边松弛n-1次松弛的意思就是如果通过from到to这条边到to会让to的距离变小就把minDist[to]更新为minDist[from]val(from-to)原因每松弛一次就会让所有已经有有效距离的节点向外走一步所以松弛n-1次就会遍历完所有从起点到终点的路径又由于每到一个节点都会经过路径更新距离更小就更新距离更大保持不变所以最后留下的一定就是最小的节点到起点的距离了。#includeiostream using namespace std; #includevector #includeclimits int main(){ int n,m,s,t,val; cinnm; vectorvectorint graph; while(m--){ cinstval; graph.push_back({s,t,val}); } vectorint minDist(n1,INT_MAX); minDist[1] 0; for(int i1;in;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) coutunconnectedendl; else coutminDist[n]endl; }