【图论】最短路径-----Dijkstra篇

文章目录【图论】最短路径Dijkstra算法朴素版代码实现堆优化图的存储实现代码结构体形式pair形式例题【图论】最短路径算法单源 / 多源支持负权边检测负权环时间复杂度适合场景Dijkstra堆优化单源不支持❌O(mlogn)无负权稀疏图绝大多数题目首选Bellman‑Ford单源支持✅O(nm)理论学习实际做题很少手写SPFA单源支持✅平均O(m)最坏O(nm)存在负权边、需要判负环无负权不要用容易被卡Floyd‑Warshall多源任意两点支持❌O(n3)点数 n 很小求全部点对最短路单源一个起点到其它所有点多源一次性得到任意两点之间最短距离能检测负权环可以判断图里有没有可以无限绕、距离越走越小的环Floyd 不能识别负环图中有负环时结果失效。最短路是图论中的经典问题即给出一个有向图一个起点一个终点问起点到终点的最短路径Dijkstra算法dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法dijkstra 算法可以同时求 起点到所有节点的最短路径权值不能为负数dijkstra 算法 同样是贪心的思路不断寻找距离 源点最近的没有访问过的节点。dijkstra三部曲选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组min_d:用来记录 每一个节点距离源点的最小距离朴素版过程初始化min_d数组初始化为longlong的最大值max 表示默认值节点0 不做处理统一从下标1 开始计算源点节点1 到自己的距离为0,所以在初始化时别忘记min_d[1]0vis数组表示该结点未被访问过选源点到哪个节点近且该节点未被访问过源点距离源点最近距离为0且未被访问。该最近节点被标记访问过​ 标记源点访问过更新非访问节点到源点的距离即更新min_d数组更新min_d数组即源点节点1 到 节点2 和 节点3的距离。源点到节点2的最短距离是1原min_d[2]max更新min_d[2]1源点到节点3的最短距离是4原min_d[3]max更新min_d[3]4选源点到哪个节点近且该节点未被访问过​ 未访问过的节点中源点到节点2距离最近选节点2该最近节点被标记访问过节点2被标记访问过更新非访问节点到源点的距离即更新min_d数组更新min_d数组即源点节点1通过 已经计算过的节点节点2 可以链接到的节点 有 节点3节点4和节点6源点透过2到节点6的最短距离是5原min_d[6]max更新min_d[6]min_d[2]g[2][6]14源点透过2到节点4的最短距离是6原min_d[4]max更新min_d[4]min_d[2]g[2][4]15源点透过2到节点3的最短距离是3原min_d[3]4更新min_d[3]min_d[2]g[2][3]12选源点到哪个节点近且该节点未被访问过​ 未访问过的节点中源点到节点3距离最近选节点3该最近节点被标记访问过节点3被标记访问过更新非访问节点到源点的距离即更新min_d数组源点透过3到节点4的最短距离是5原min_d[4]6更新min_d[4]min_d[3]g[3][4]32选源点到哪个节点近且该节点未被访问过​ 距离源点最近且没有被访问过的节点有节点4 和 节点6距离源点距离都是 5 min_d[4] 5min_d[6] 5 选哪个节点都可以。该最近节点被标记访问过​ 节点4被标记访问过更新非访问节点到源点的距离即更新min_d数组源点透过4到节点5的最短距离是8原min_d[5]max更新min_d[5]min_d[4]g[4][5]53选源点到哪个节点近且该节点未被访问过​ 距离源点最近且没有被访问过的节点是节点6距离源点距离是 5该最近节点被标记访问过​ 节点6 被标记访问过更新非访问节点到源点的距离即更新min_d数组源点透过6到节点7的最短距离是14原min_d[7]max更新min_d[7]min_d[6]g[6][7]59选源点到哪个节点近且该节点未被访问过​ 距离源点最近且没有被访问过的节点是节点5距离源点距离是 8该最近节点被标记访问过​ 节点5 被标记访问过更新非访问节点到源点的距离即更新min_d数组源点透过5到节点7的最短距离是12原min_d[7]14更新min_d[7]min_d[5]g[5][7]84选源点到哪个节点近且该节点未被访问过​ 距离源点最近且没有被访问过的节点是节点7距离源点距离是 12该最近节点被标记访问过​ 节点7被标记访问过更新非访问节点到源点的距离即更新min_d数组节点7加入并不用更新数组最后我们要求起点节点1 到终点 节点7的距离。那么起到节点1到终点节点7的最短距离就是min_d[7] 12最终路径代码实现#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpairll,ll#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;constll MAXN5005;constll inf0x3f3f3f3f;usingnamespacestd;ll n,m;ll l,r,v;intmain(){IOS cinnm;vectorvectorllg(n1,vectorll(n1,LLONG_MAX));while(m--){cinlrv;g[l][r]v;}vectorboolvis(n1,false);vectorllmin_d(n1,LLONG_MAX);ll start1;ll endn;min_d[1]0;for(ll i1;in;i){ll min_vLLONG_MAX;ll cnt1;for(ll j1;jn;j){if(!vis[j]min_d[j]min_v){min_vmin_d[j];cntj;}}vis[cnt]true;for(ll j1;jn;j){if(!vis[j]g[cnt][j]!LLONG_MAXmin_d[cnt]g[cnt][j]min_d[j]){min_d[j]min_d[cnt]g[cnt][j];}}}if(min_d[end]LLONG_MAX){cout-1endl;}else{coutmin_d[end]endl;}// coutfixedsetprecision(x) ;return0;}时间复杂度O(n2)空间复杂度O(n2)堆优化(以边进行优化)图的存储邻接矩阵邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。例如grid[2][5] 6表示 节点 2 链接 节点5 为有向图节点2 指向 节点5边的权值为6如果想表示无向图即grid[2][5] 6grid[5][2] 6表示节点2 与 节点5 相互连通权值为6在一个 n 节点数为8 的图中就需要申请 8 * 8 这么大的空间有一条双向边即grid[2][5] 6grid[5][2] 6这种表达方式邻接矩阵 在 边少节点多的情况下会导致申请过大的二维数组造成空间浪费。而且在寻找节点链接情况的时候需要遍历整个矩阵即 n * n 的时间复杂度同样造成时间浪费。优点表达方式简单易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图在边数接近顶点数平方的图中邻接矩阵是一种空间效率较高的表示方法邻接表利用数组链表的方式表示优点对于稀疏图的存储只需要存储边空间利用率高遍历节点链接情况相对容易在朴素版中我们是利用一个大循环去跑每个节点是从节点出发的在上一个图中发现是没有权值的我们可以借助pair和结构体去存储pairvectorlistpairint,intg(n1);结构体structp{ll point;ll v;};vectorlistpg;先前是在通过遍历节点来遍历边而现在我们用堆优化时就是在直接遍历边且是通过小顶堆来对边进行排序直接选择距离源点最近的节点实现代码结构体形式结构体形式的cmp函数会有点不好写因为priority_queue不能自己cmp// 这样写编译报错不允许boolcmp(pairll,lla,pairll,llb){returna.seb.se;}priority_queuepairll,ll,vectorpairll,ll,cmppq;#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpairll,ll#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;constll MAXN5005;constll inf0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};classmycomparison{public:booloperator()(constpairll,lllhs,constpairll,llrhs){returnlhs.serhs.se;}};usingnamespacestd;ll n,m;ll p1,p2,val;intmain(){IOS cinnm;vectorlistEdgegrid(n1);for(ll i1;im;i){cinp1p2val;grid[p1].emplace_back(p2,val);}ll start1;ll endn;vectorllminDist(n1,inf);vectorboolvisited(n1,false);priority_queuepairll,ll,vectorpairll,ll,mycomparisonpq;pq.push({start,0});minDist[start]0;while(!pq.empty()){pairll,llcurpq.top();pq.pop();if(visited[cur.fi])continue;visited[cur.fi]true;for(Edge edge:grid[cur.fi]){ll vedge.to;ll wedge.val;if(!visited[v]minDist[cur.fi]!infminDist[cur.fi]wminDist[v]){minDist[v]minDist[cur.fi]w;pq.push({v,minDist[v]});}}}if(minDist[end]inf){cout-1endl;}else{coutminDist[end]endl;}return0;}pair形式#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpairll,ll#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;constll MAXN5005;constll inf0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};ll n,m;ll l,r,v;intmain(){IOS cinnm;vectorlistEdgeg(n1);for(ll i1;im;i){cinlrv;g[l].emplace_back(r,v);}ll start1;ll endn;vectorllmin_d(n1,inf);vectorboolvis(n1,false);priority_queuePLL,vectorPLL,greaterPLLq;q.push({0,start});min_d[start]0;while(!q.empty()){PLL cq.top();q.pop();ll disc.fi;ll uc.se;if(vis[u])continue;vis[u]true;for(Edge edge:g[u]){ll vedge.to;ll wedge.val;if(!vis[v]min_d[u]!infmin_d[u]wmin_d[v]){min_d[v]min_d[u]w;q.push({min_d[v],v});}}}if(min_d[end]inf){cout-1endl;}else{coutmin_d[end]endl;}return0;}例题参加科学大会#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpairll,ll#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;constll MAXN5005;constll inf0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};ll n,m;ll l,r,v;intmain(){IOS cinnm;vectorlistEdgeg(n1);for(ll i1;im;i){cinlrv;g[l].emplace_back(r,v);}ll start1;ll endn;vectorllmin_d(n1,inf);vectorboolvis(n1,false);priority_queuePLL,vectorPLL,greaterPLLq;q.push({0,start});min_d[start]0;while(!q.empty()){PLL cq.top();q.pop();ll disc.fi;ll uc.se;if(vis[u])continue;vis[u]true;for(Edge edge:g[u]){ll vedge.to;ll wedge.val;if(!vis[v]min_d[u]!infmin_d[u]wmin_d[v]){min_d[v]min_d[u]w;q.push({min_d[v],v});}}}if(min_d[end]inf){cout-1endl;}else{coutmin_d[end]endl;}return0;}