数据结构之最短路径

1、迪杰斯特拉算法（Dijkstra Algorithm）

迪杰斯特拉算法是⼀个单源点的⼀个最短路径算法，也就是说，我们这个算法会求得从⼀个顶点到其所有顶点的最短路径。
迪杰斯特拉算法可以计算指定顶点到其他顶点之间的最短路径，那么我就可以通过指定网络中的每⼀个顶点为源点，重复执⾏迪杰斯特拉算法 n 次，这样便可以得到每⼀对顶点之间的最短路径，这种方式的时间复杂度为O（n^3） 。

#include<iostream>#include<vector>#include<climits>usingnamespacestd;constintINF=INT_MAX/2;// 防止加法溢出// 单源Dijkstra：start为源点，返回start到所有点的最短路vector<int>dijkstraSingle(constvector<vector<int>>&graph,intn,intstart){vector<int>dist(n,INF);vector<bool>vis(n,false);dist[start]=0;for(inti=0;i<n;++i){// 1. 找未访问、距离最小的点uintu=-1;intminVal=INF;for(intj=0;j<n;++j){if(!vis[j]&&dist[j]<minVal){minVal=dist[j];u=j;}}if(u==-1)break;vis[u]=true;// 2. 松弛更新for(intv=0;v<n;++v){if(!vis[v]&&graph[u][v]!=INF){if(dist[v]>dist[u]+graph[u][v]){dist[v]=dist[u]+graph[u][v];}}}}returndist;}// 对每个顶点执行一次Dijkstra，得到全点对最短路矩阵vector<vector<int>>dijkstraAllPair(constvector<vector<int>>&graph,intn){vector<vector<int>>res;for(ints=0;s<n;++s){res.push_back(dijkstraSingle(graph,n,s));}returnres;}intmain(){// 4个顶点邻接矩阵intn=4;vector<vector<int>>graph={{0,2,INF,6},{INF,0,3,INF},{INF,INF,0,1},{INF,INF,INF,0}};vector<vector<int>>allDist=dijkstraAllPair(graph,n);cout<<"===== 多次Dijkstra 全源最短路径矩阵 ====="<<endl;for(auto&row:allDist){for(intx:row){if(x>=INF)cout<<"∞ ";elsecout<<x<<" ";}cout<<endl;}return0;}

2、弗洛伊德算法（Floyd Algorithm）

弗洛伊德算法是全源点最短路径算法，也就是说，该算法单次运行就能直接求出图中任意一对顶点之间的最短路径，不需要多次重复执行算法。
弗洛伊德算法不需要单独指定源点，而是以整个图的邻接距离矩阵为基础，依次把网络中每一个顶点 k 当作中转中间点，循环执行松弛操作：对任意起点 i、终点 j，判断路径 i→k→j 是否比当前 i→j 的直接路径更短，若更短就更新两点间最短距离；完整遍历全部 n 个顶点作为中转点后，矩阵内 i 行 j 列的值就是顶点 i 到顶点 j 的最短路径，仅需一轮三层循环即可得到每一对顶点之间的最短路径，这种方式的时间复杂度同样为 (O(n^3))。

#include<iostream>#include<vector>#include<climits>usingnamespacestd;constintINF=INT_MAX/2;vector<vector<int>>floyd(constvector<vector<int>>&graph,intn){// 复制邻接矩阵为距离矩阵vector<vector<int>>dist=graph;// k：中转点 i起点 j终点for(intk=0;k<n;++k)for(inti=0;i<n;++i)for(intj=0;j<n;++j){if(dist[i][k]!=INF&&dist[k][j]!=INF){dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}returndist;}intmain(){intn=4;vector<vector<int>>graph={{0,2,INF,6},{INF,0,3,INF},{INF,INF,0,1},{INF,INF,INF,0}};vector<vector<int>>dist=floyd(graph,n);cout<<"\n===== Floyd弗洛伊德 全源最短路径矩阵 ====="<<endl;for(auto&row:dist){for(intx:row){if(x>=INF)cout<<"∞ ";elsecout<<x<<" ";}cout<<endl;}return0;}