学习搭建网站,网络架构1788,jsp网站开发存在的问题,零成本做网站1.前言 最短路径算法是在图论的基础上讲解的#xff0c;如果你还不知道图论的相关知识的话#xff0c;可以阅读下面几篇文章。 [高阶数据结构四] 初始图论_初始图结构-CSDN博客
[高阶数据结构五] 图的遍历和最小生成树_图的遍历和生成树求解-CSDN博客
本章重点#xff1a;…1.前言 最短路径算法是在图论的基础上讲解的如果你还不知道图论的相关知识的话可以阅读下面几篇文章。 [高阶数据结构四] 初始图论_初始图结构-CSDN博客
[高阶数据结构五] 图的遍历和最小生成树_图的遍历和生成树求解-CSDN博客
本章重点
本章主要讲解图论的三种算法---DijkstraBallman-FordFloyd-Warshall算法。
2.单源最短路径
所谓的单源最短路径,也就是从图中任意一点出发, 到图中每个节点的最短路径,也就是最小的权值和。
举个例子 为了要统计源点Srci即s到yztx四点的最短路径通常使用两个数组来解决。
其中一个表示的是从源点到当前点的最短路径的权值
另外一个表示的是从源点到当前点最短路径的路径是什么。
//存储任意点到图中其他点的最短路径的权值vectorW dist//记录srci-其他顶点最短路径父顶点数组vectorint parentPath这么说可能有点抽象看如下图。 数组下标x处对应的是t所在位置的下标而t处对应的下标所在的位置是y。
dist中dist[4]表示从源点到x的最短路径为9。
3.Dijkstra算法 针对一个带权有向图 G 将所有结点分为两组 S 和 Q S 是已经确定最短路径的结点集合在初始时 为空初始时就可以将源节点s 放入毕竟源节点到自己的代价是 0 Q 为其余未确定最短路径 的结点集合每次从 Q 中找出一个起点到该结点代价最小的结点 u 将 u 从 Q 中移出并放入 S 中对 u 的每一个相邻结点 v 进行松弛操作 。 什么是松弛操作呢 松弛即对每一个相邻结点 v 判断源节点 s 到结点 u 的代价与u 到 v 的代价之和是否比原来 s 到 v 的代价更小若代价比原来小则要将 s 到 v 的代价更新 为s 到 u 与 u 到 v 的代价之和否则维持原样。 这样说有点抽象--但是如果你阅读了前面两篇文章你会发现这个算法和Prim算法是有点类似的。
举例如下 a处唯一确定的节点就是s,其余均是不确定的。在这里面找出一个与A直接相连且路径是最短的出来然后这个值那么一定是可以唯一确定的。
b处也用a处的方法然后可以确定的节点是s,y其余均为不确定的。
依次重复有几个结点那么重复几次一定可以把所有的节点确定下来。这里的前提是权值均为正不可以有负的。后续解释为什么。
代码如下
void Dijkstra(const V src, vectorW dist, vectorint parentPath){//dist[i]表示srci到i位置的最短路径的权值//parentPath[i]表示推导出当前节点的下标.//即srci-B位置的最小权值是由srci-A-B推导而来,所以存储的是A的下标size_t n _ver.size();dist.resize(n, int_MAX);parentPath.resize(n, -1);//-1表示初始时没有路径能走到int srci GetIndex(src);dist[srci] 0;dist[srci] W();parentPath[srci] srci;vectorbool visited(n, false);//n个节点,一共会更新n次,也可以判断visited数组中的元素是否全为truefor (int s 0; s n; s){//每次找出dist中没有遍历过的当前的最小的权值来做确定的顶点及边int u 0;//表示顶点int min int_MAX;//表示srci-u的权值for (int i 0; i n; i){if (visited[i] false dist[i] min){u i;min dist[i];}}//到这里就找到了最小的visited[u] true;//开始进行松弛操作即从srci-u-v的权值是否比srci-v的权值小小的话就在dist中换掉for (int v 0; v n; v){//这里松弛操作还有一个关键点就是已经选定了的即在visited里面是true的后续哪怕找到了//比当前小的路径也不在进行松弛操作了。理论上是不可能的含有负权值除外if (visited[v]false_martix[u][v] ! int_MAX dist[v] dist[u] _martix[u][v]){dist[v] dist[u] _martix[u][v];parentPath[v] u;//表示u这个顶点-v顶点}}}}
这个算法是不支持有负权值的这是因为一旦有了负权值你之前唯一确定的点可能就不是最短路径的值了。因为这里出现了环那么可能出现的问题是:一直在环里面兜圈子那么就会出现无穷小的情况。
例如 4.BellMan-Ford算法
这个算法能够解决带有负权值的问题。 他是通过暴力的解法来搞定这个问题的。 它的时间复杂度是O(N^3). 它的思路就是以所有顶点为起始点,更新所有相连的边。 代码如下
bool BellmanFord(const V src, vectorW dist,vectorint parentPath){size_t n _ver.size();dist.resize(n, int_MAX);parentPath.resize(n, -1);//-1表示暂时所有的都没有通路int srci GetIndex(src);dist[srci] W();for (int k 0; k n-1; k){//加这个条件是有时候可能走3轮就不会再走后面的循环了为了节省时间bool exchange false;//开始暴力遍历n-1条边并且更新权值cout 第[ k 轮] endl;for (int i 0; i n; i){for (int j 0; j n; j){//srci -i i- j 与srci-j的比较if (_martix[i][j] ! int_MAX dist[i] _martix[i][j] dist[j]){cout [ _ver[i] ] - _ver[j] : \ _martix[i][j] endl;dist[j] dist[i] _martix[i][j];parentPath[j] i;exchange true;}}}//到这里第一遍n-1条边的权值已经更新完了但是有可能导致的因数是前面确定的边的值可能不是最小值//前面确定边的值必须由后面确定边的值推导而来。一次暴力遍历n-1条边可以至少确定一个顶点有n个//顶点所以至少要遍历n-1遍if (exchange false) break;}//这里判断负权值的回路是否构成了环for (int i 0; i n; i){for (int j 0; j n; j){//srci -i i- j 与srci-j的比较if (_martix[i][j] ! int_MAX dist[i] _martix[i][j] dist[j]){return false;}}}return true;}
5.多源最短路径问题
简单的来说多源最短路径问题就是任意两点间的最短路径的权值以及走过的节点是什么。
那么这就需要两个二维数组来表示上述两个情况了。 一个二维数组存储顶点i-j的最短路径的权值和, 另外一个数组存储 (i,j)的父节点下标. i,j是最短路径的节点。 6.Folyd-WarShall算法
Floyd算法考虑的是一条最短路径的中间节点即简单路径p{v1,v2,…,vn}上除v1和vn的任意节 点。设k是p的一个中间节点那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1p2。p1是从i到k且中间节点属于{12…k-1}取得的一条最短路径。p2是从k到j且中间节点属于{12…k-1}取得的一条最短路径 举个例子 代码如下
void FloydWarShall(vectorvectorW vvDist, vectorvectorint vvParentPath){//任意两点的最短路径//1.初始化size_t n _ver.size();vvDist.resize(n);vvParentPath.resize(n);for (int i 0; i n; i){vvDist[i].resize(n, int_MAX);vvParentPath[i].resize(n, -1);}//先初始化那些直接相连的for (int i 0; i n; i){for (int j 0; j n; j){if (i j){vvDist[i][j] 0;vvParentPath[i][j] -1;}if (_martix[i][j] ! int_MAX){vvDist[i][j] _martix[i][j];vvParentPath[i][j] i;}}}//任意两点间的最短路径---abcdef 求a-f之间的最短路径假设中间点为k,//可能经过k点也可能不经过k点//若经过k点dist[i][j]dist[i][k]dist[k][j]//不经过k点的话那么dist[i][j]dist[i][j],此时i-j之间是少了k点这个值的//那么问题就转换成找k点了那么k点是谁呢 a-f k点可能是b c d e//若求的是b-e最短路径呢 那么k点可能是a c e f。//通过上述分析发现任意一个点都有可能成为k点。for (int k 0; k n; k){for (int i 0; i n; i){for (int j 0; j n; j){if (vvDist[i][k] ! int_MAX vvDist[k][j] ! int_MAX vvDist[i][k] vvDist[k][j] vvDist[i][j]){vvDist[i][j] vvDist[i][k] vvDist[k][j];vvParentPath[i][j] vvParentPath[k][j];//这里为什么不直接是k呢//首先如果k是推出j的上一个顶点那么vvp[k][j]一定放的是k//那么如果k不是推出j的上一个顶点呢那么就不能填k//但是上一个顶点一定存放在vvp[k][j]里面}}}}
7.总结 这些算法都比较抽象博主花了很大很大的功夫才理解他们如果真要完全手撕那么我想博主起码最少需要几个小时因此就算不会手撕也没有关系只需要知道思路即可。在面试中能讲出思路也是一个加分项呢。
