文章目录
- 【图论】最短路径
- 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]=0； vis数组表示该结点未被访问过
- 选源点到哪个节点近且该节点未被访问过
源点距离源点最近，距离为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]=1+4 - 源点透过2到节点4的最短距离是6，<原
min_d[4]=max，更新min_d[4]=min_d[2]+g[2][4]=1+5 - 源点透过2到节点3的最短距离是3，<原
min_d[3]=4，更新min_d[3]=min_d[2]+g[2][3]=1+2
- 选源点到哪个节点近且该节点未被访问过
未访问过的节点中，源点到节点3距离最近，选节点3
该最近节点被标记访问过
节点3被标记访问过
更新非访问节点到源点的距离（即更新min_d数组）
- 源点透过3到节点4的最短距离是5，<原
min_d[4]=6，更新min_d[4]=min_d[3]+g[3][4]=3+2
- 选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点，有节点4 和 节点6，距离源点距离都是 5 （min_d[4] = 5，min_d[6] = 5） ，选哪个节点都可以。
- 该最近节点被标记访问过
节点4被标记访问过
- 更新非访问节点到源点的距离（即更新min_d数组）
- 源点透过4到节点5的最短距离是8，<原
min_d[5]=max，更新min_d[5]=min_d[4]+g[4][5]=5+3
- 选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点，是节点6，距离源点距离是 5
- 该最近节点被标记访问过
节点6 被标记访问过
- 更新非访问节点到源点的距离（即更新min_d数组）
- 源点透过6到节点7的最短距离是14，<原
min_d[7]=max，更新min_d[7]=min_d[6]+g[6][7]=5+9
- 选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点，是节点5，距离源点距离是 8
- 该最近节点被标记访问过
节点5 被标记访问过
- 更新非访问节点到源点的距离（即更新min_d数组）
- 源点透过5到节点7的最短距离是12，<原
min_d[7]=14，更新min_d[7]=min_d[5]+g[5][7]=8+4
- 选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点，是节点7，距离源点距离是 12
- 该最近节点被标记访问过
节点7被标记访问过
- 更新非访问节点到源点的距离（即更新min_d数组）
节点7加入，并不用更新数组
最后我们要求起点（节点1） 到终点 （节点7）的距离。
那么起到（节点1）到终点（节点7）的最短距离就是min_d[7] =12
最终路径
代码实现
#include<bits/stdc++.h>#definelllonglong#defineendl'\n'#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpair<ll,ll>#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;usingnamespacestd;constll MAXN=5005;constll inf=0x3f3f3f3f;usingnamespacestd;ll n,m;ll l,r,v;intmain(){IOS cin>>n>>m;vector<vector<ll>>g(n+1,vector<ll>(n+1,LLONG_MAX));while(m--){cin>>l>>r>>v;g[l][r]=v;}vector<bool>vis(n+1,false);vector<ll>min_d(n+1,LLONG_MAX);ll start=1;ll end=n;min_d[1]=0;for(ll i=1;i<=n;i++){ll min_v=LLONG_MAX;ll cnt=1;for(ll j=1;j<=n;j++){if(!vis[j]&&min_d[j]<min_v){min_v=min_d[j];cnt=j;}}vis[cnt]=true;for(ll j=1;j<=n;j++){if(!vis[j]&&g[cnt][j]!=LLONG_MAX&&min_d[cnt]+g[cnt][j]<min_d[j]){min_d[j]=min_d[cnt]+g[cnt][j];}}}if(min_d[end]==LLONG_MAX){cout<<-1<<endl;}else{cout<<min_d[end]<<endl;}// cout<<fixed<<setprecision(x)<< ;return0;}- 时间复杂度：O(n2)
- 空间复杂度：O(n2)
堆优化
(以边进行优化)
图的存储
邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
例如：
grid[2][5] = 6，表示 节点 2 链接 节点5 为有向图，节点2 指向 节点5，边的权值为6如果想表示无向图，即：
grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6
在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间，有一条双向边，即：
grid[2][5] = 6，grid[5][2] = 6这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。
而且在寻找节点链接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。
优点：
- 表达方式简单，易于理解
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法
邻接表
利用数组+链表的方式表示
优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点链接情况相对容易
在朴素版中我们是利用一个大循环去跑每个节点，是从节点出发的
在上一个图中发现是没有权值的，我们可以借助
pair和结构体去存储pair
vector<list<pair<int,int>>>g(n+1);结构体
structp{ll point;ll v;};vector<list<p>>g;先前是在通过遍历节点来遍历边，而现在我们用堆优化时，就是在直接遍历边，且是通过小顶堆来对边进行排序，直接选择距离源点最近的节点
实现代码
结构体形式
结构体形式的cmp函数会有点不好写，因为priority_queue不能自己cmp
// 这样写编译报错，不允许boolcmp(pair<ll,ll>a,pair<ll,ll>b){returna.se>b.se;}priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,cmp>pq;#include<bits/stdc++.h>#definelllonglong#defineendl'\n'#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpair<ll,ll>#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;usingnamespacestd;constll MAXN=5005;constll inf=0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};classmycomparison{public:booloperator()(constpair<ll,ll>&lhs,constpair<ll,ll>&rhs){returnlhs.se>rhs.se;}};usingnamespacestd;ll n,m;ll p1,p2,val;intmain(){IOS cin>>n>>m;vector<list<Edge>>grid(n+1);for(ll i=1;i<=m;i++){cin>>p1>>p2>>val;grid[p1].emplace_back(p2,val);}ll start=1;ll end=n;vector<ll>minDist(n+1,inf);vector<bool>visited(n+1,false);priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,mycomparison>pq;pq.push({start,0});minDist[start]=0;while(!pq.empty()){pair<ll,ll>cur=pq.top();pq.pop();if(visited[cur.fi])continue;visited[cur.fi]=true;for(Edge edge:grid[cur.fi]){ll v=edge.to;ll w=edge.val;if(!visited[v]&&minDist[cur.fi]!=inf&&minDist[cur.fi]+w<minDist[v]){minDist[v]=minDist[cur.fi]+w;pq.push({v,minDist[v]});}}}if(minDist[end]==inf){cout<<-1<<endl;}else{cout<<minDist[end]<<endl;}return0;}pair形式
#include<bits/stdc++.h>#definelllonglong#defineendl'\n'#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpair<ll,ll>#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;usingnamespacestd;constll MAXN=5005;constll inf=0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};ll n,m;ll l,r,v;intmain(){IOS cin>>n>>m;vector<list<Edge>>g(n+1);for(ll i=1;i<=m;i++){cin>>l>>r>>v;g[l].emplace_back(r,v);}ll start=1;ll end=n;vector<ll>min_d(n+1,inf);vector<bool>vis(n+1,false);priority_queue<PLL,vector<PLL>,greater<PLL>>q;q.push({0,start});min_d[start]=0;while(!q.empty()){PLL c=q.top();q.pop();ll dis=c.fi;ll u=c.se;if(vis[u])continue;vis[u]=true;for(Edge edge:g[u]){ll v=edge.to;ll w=edge.val;if(!vis[v]&&min_d[u]!=inf&&min_d[u]+w<min_d[v]){min_d[v]=min_d[u]+w;q.push({min_d[v],v});}}}if(min_d[end]==inf){cout<<-1<<endl;}else{cout<<min_d[end]<<endl;}return0;}例题
参加科学大会
#include<bits/stdc++.h>#definelllonglong#defineendl'\n'#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#definePLLpair<ll,ll>#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;usingnamespacestd;constll MAXN=5005;constll inf=0x3f3f3f3f3f3f3f3f;structEdge{ll to,val;Edge(ll t,ll w):to(t),val(w){}};ll n,m;ll l,r,v;intmain(){IOS cin>>n>>m;vector<list<Edge>>g(n+1);for(ll i=1;i<=m;i++){cin>>l>>r>>v;g[l].emplace_back(r,v);}ll start=1;ll end=n;vector<ll>min_d(n+1,inf);vector<bool>vis(n+1,false);priority_queue<PLL,vector<PLL>,greater<PLL>>q;q.push({0,start});min_d[start]=0;while(!q.empty()){PLL c=q.top();q.pop();ll dis=c.fi;ll u=c.se;if(vis[u])continue;vis[u]=true;for(Edge edge:g[u]){ll v=edge.to;ll w=edge.val;if(!vis[v]&&min_d[u]!=inf&&min_d[u]+w<min_d[v]){min_d[v]=min_d[u]+w;q.push({min_d[v],v});}}}if(min_d[end]==inf){cout<<-1<<endl;}else{cout<<min_d[end]<<endl;}return0;}
