数据结构之最短路径

1、迪杰斯特拉算法Dijkstra Algorithm迪杰斯特拉算法是⼀个单源点的⼀个最短路径算法也就是说我们这个算法会求得从⼀个顶点到其所有顶点的最短路径。迪杰斯特拉算法可以计算指定顶点到其他顶点之间的最短路径那么我就可以通过指定网络中的每⼀个顶点为源点重复执⾏迪杰斯特拉算法 n 次这样便可以得到每⼀对顶点之间的最短路径这种方式的时间复杂度为On^3 。#includeiostream#includevector#includeclimitsusingnamespacestd;constintINFINT_MAX/2;// 防止加法溢出// 单源Dijkstrastart为源点返回start到所有点的最短路vectorintdijkstraSingle(constvectorvectorintgraph,intn,intstart){vectorintdist(n,INF);vectorboolvis(n,false);dist[start]0;for(inti0;in;i){// 1. 找未访问、距离最小的点uintu-1;intminValINF;for(intj0;jn;j){if(!vis[j]dist[j]minVal){minValdist[j];uj;}}if(u-1)break;vis[u]true;// 2. 松弛更新for(intv0;vn;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得到全点对最短路矩阵vectorvectorintdijkstraAllPair(constvectorvectorintgraph,intn){vectorvectorintres;for(ints0;sn;s){res.push_back(dijkstraSingle(graph,n,s));}returnres;}intmain(){// 4个顶点邻接矩阵intn4;vectorvectorintgraph{{0,2,INF,6},{INF,0,3,INF},{INF,INF,0,1},{INF,INF,INF,0}};vectorvectorintallDistdijkstraAllPair(graph,n);cout 多次Dijkstra 全源最短路径矩阵 endl;for(autorow:allDist){for(intx:row){if(xINF)cout∞ ;elsecoutx ;}coutendl;}return0;}2、弗洛伊德算法Floyd Algorithm弗洛伊德算法是全源点最短路径算法也就是说该算法单次运行就能直接求出图中任意一对顶点之间的最短路径不需要多次重复执行算法。弗洛伊德算法不需要单独指定源点而是以整个图的邻接距离矩阵为基础依次把网络中每一个顶点 k 当作中转中间点循环执行松弛操作对任意起点 i、终点 j判断路径 i→k→j 是否比当前 i→j 的直接路径更短若更短就更新两点间最短距离完整遍历全部 n 个顶点作为中转点后矩阵内 i 行 j 列的值就是顶点 i 到顶点 j 的最短路径仅需一轮三层循环即可得到每一对顶点之间的最短路径这种方式的时间复杂度同样为 (O(n^3))。#includeiostream#includevector#includeclimitsusingnamespacestd;constintINFINT_MAX/2;vectorvectorintfloyd(constvectorvectorintgraph,intn){// 复制邻接矩阵为距离矩阵vectorvectorintdistgraph;// k中转点 i起点 j终点for(intk0;kn;k)for(inti0;in;i)for(intj0;jn;j){if(dist[i][k]!INFdist[k][j]!INF){dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]);}}returndist;}intmain(){intn4;vectorvectorintgraph{{0,2,INF,6},{INF,0,3,INF},{INF,INF,0,1},{INF,INF,INF,0}};vectorvectorintdistfloyd(graph,n);cout\n Floyd弗洛伊德 全源最短路径矩阵 endl;for(autorow:dist){for(intx:row){if(xINF)cout∞ ;elsecoutx ;}coutendl;}return0;}