【PHP数据结构】图的应用：最短路径

上一篇文章的最小生成树，是不是觉得意犹未尽？我不知道你掌握得如何。Prim和Kruskal这两个算法的原理你搞清楚了吗？面试的时候写不出来，至少也要给个大概的思路。当然，如果你是准备考研的学生，你一定要看懂并记住整个算法的代码。什么是最短路径？今天我们研究的是图应用中的另一个经典问题，即最短路径问题。这个问题不同于最小生成树。最小生成树的要求是连接所有的节点，走权重最小的路由。最短路径是指从一个顶点到另一个顶点的权重最小的路径。这条路径不一定包含在最小生成树中，所以它们的关系不大。从这个图中可以看出，我们从节点1到节点2的最短路径是2。那么从节点1到节点3呢？不是权重为6的直接中间路径，而是1->2->3的路径，也就是权重加起来为5的路径。那我们再来看节点3。从它到节点1的最短路径应该是路径3->4->1，也就是权重为6的路径，不是中间那条直线的权重。7条路径。没错，这就是最短路径的概念。在最短路径中，我们一般解决的是单向图的问题，但是在现实生活中呢？最典型的地图相关应用其实就是双向图。不过，这并不影响我们的学习。我们可以将此示例图中的节点视为城市火车站。即使是连接节点1和节点3的火车线路，来去的时间也不一定相同。的。例如，长沙至北京的Z2次列车总运行时间为14小时42分钟，而返回的Z1次列车则需要14小时10分钟。那我们是不是可以选择其他的火车，比如长沙到石家庄一趟火车可能只需要8个小时，然后从石家庄到北京只需要2个小时，所以我们选择这条线路的总时间也就只有10个小时（当然，这只是举个例子，非高铁的情况下大家肯定会选择始发站的火车多坐）。多源最短路径Floyd算法首先，我们来谈谈多源最短路径算法。那么什么是多源呢？其实这个算法可以得到所有节点和所有节点之间的最短路径。没错，有了这个算法，无论从哪个节点到哪个节点，都是一次性计算出它们之间的最短路径。很神奇吗？不不不，更神奇的是，你怎么称呼哦！我的上帝！是它的核心代码，只有五行！！函数Floyd($graphArr){$n=count($graphArr);for($k=1;$k<=$n;$k++){//让k为传递的节点for($i=1;$i<=$n;$i++){for($j=1;$j<=$n;$j++){//如果传递k个节点可以使i到j的路径更短，那么j之间的更新就是经过k传递后的结果if($graphArr[$i][$j]>$graphArr[$i][$k]+$graphArr[$k][$j]){$graphArr[$i][$j]=$graphArr[$i][$k]+$graphArr[$k][$j];}}}}for($i=1;$i<=$n;$i++){for($j=1;$j<=$n;$j++){echo$graphArr[$i][$j],'';}echoPHP_EOL;}}//请输入节点数：4//请输入边数：8//请以访问权限格式输入边数：122//请以访问权限格式输入边数：136//Pleaseinputsidesintheformatofaccessrights:144//Pleaseinputside,formatisaccessright:233//Pleaseinputside,formatisaccessright:317//请输入边，格式为访问权限：233//请输入边，格式为访问权限：317//inputside,formatisaccessright:341//Pleaseinputside,formatisAccessright:415//请输入side,formatisAccessright:4312//0254//9034//6801//57100我们可以先验证一下结果，也就是注释中的最终输出矩阵。从节点1到节点2、3、4的最短距离是2、5、4。从节点3到节点1、2、4的最短距离是6、8、1。也就是说，原图的邻接矩阵变成了最短路径的矩阵。每行代表每个节点到其他节点的最短距离。嗯，结果还可以，那么最后写的代码是怎样的呢？这是什么克？别着急，我们一步步来看。假设两点之间的距离不是最短的，那么一定有另外一个点作为媒介，从i点跳到这个点，再跳到j点。如果j很近，我们就把这个点定义为k点，但是不知道去哪个节点，k可能不止一个，可能我们从i到j要经过很多k，这时候，我们将从k开始遍历，即第一层循环在第一层循环下，进行我们正常的i和j遍历循环，得到从i直接到j的长度，即i。这时由于最外层k的存在，我们也知道了i从k走的话k到j的长度，即i+k的距离是显而易见的。如果i+k的距离比i短，则更新i的值为i+k。内部i和j循环完成后，第一个节点作为媒体跳转的遍历也完成了，当前矩阵中节点之间的权值已经通过了第一个节点是经过媒体的最短路径.然而，这是不准确的。可能我们经过i,k1,k2,j的路径是最短的，所以外层k循环继续遍历和第二个节点作为中间节点往复，直到所有节点都当过中间节点一次，并且我们得到一个最短路径的矩阵图，这是我们上面测试代码中输出的结果。我们以节点4和节点3来说明。我们定义4为i，节点3为j。初始化的时候i是12，这个是没有问题的。单向图中带箭头的边的权值是12。那么当k为1时，也就是我们经过节点1，看路径是否变短了，那么i为5，k为6，OK，路径变为11，i的值变为11。同时，当i为4，j为2时，在k的本次循环中，两者的最短路径也被赋值为7=1。开始的时候，4和2之间没有直接的边，但是现在在节点1的连接下，他们有了一条路径，即4=4+1=7。当k为2时，i为11，然后如上所述，我是4。即7，k为3，路径再次收缩，i+k=10，i现在又是10。循环继续，但是这条路径上没有更小的值，所以到最后的4的最短路径是10。你觉得头晕吗？拿出笔自己在纸上或者笔记本上画，画出当前最短路径矩阵在k的每一步变成了什么。这样画一次，你就会立刻知道弗洛伊德算法的核心奥秘。不得不说，前人的智慧真是伟大，也不过是前人罢了。其实Floyd老大在1962年才发表了这个算法，但是这个算法的核心思想是数学中的动态规划思想。所以，算法和数学是分不开的。你们哪位大佬不是数学界的一把手。单源最短路径Dijkstra算法说完多源最短路径，再说一个大家熟知的单源最短路径算法。上面的multi-source虽然很好，但是它的时间复杂度，也就是时间效率实在是太差了。如果没看错的话，三个N次循环嵌套就是O(N3)。如果你的数据多一点，你基本上可以从哦！我的上帝！哦！FxxK！而在大多数情况下，我们的需求会固定的寻找从一点到另一点的最短路径问题，即单源最短路径问题。这时候就可以使用这种效率稍微高一点的算法来快速求解。//origin表示源点，也就是我们希望看到的从哪个节点到其他节点的最短路径functionDijkstra($graphArr,$origin){$n=count($graphArr);$dis=[];//记录最小值$book=[];//记录节点是否被访问//初始化源点到每个点的权重for($i=1;$i<=$n;$i++){$dis[$i]=$graphArr[$原点][$i];//源点到其他点的默认权重$book[$i]=0;//没有一个节点被访问}$book[$origin]=1;//源节点本身被标记为已访问//核心算法($i=1;$i<=$n-1;$i++){$min=INFINITY;//找到距离目标节点最近的Nodefor($j=1;$j<=$n;$j++){//如果该节点没有被访问过，且当前节点的权重小于min价值如果（$book[$j]==0&&$dis[$j]<$min）{$min=$dis[$j];//min改为当前节点的路径值$u=$j;//变量u成为当前节点}//遍历所有节点后，u是最近的顶点}$book[$u]=1;//将u标记为已访问($v=1;$v<=$n;$v++){//如果[u][v]顶点小于无穷大if($graphArr[$u][$v]$dis[$u]+$graphArr[$u][$v]){//将当前dis[v]分配给dis[u]+g[u][v]$dis[$v]=$dis[$u]+$graphArr[$u][$v];}}}//最近节点完成，继续下一个最近节点}for($i=1;$i<=$n;$i++){echo$dis[$i],PHP_EOL;}}//请输入节点数：4//请输入边数：8//请输入边数，格式为In/OutRight:122//请输入边数，格式为accessright:136//请输入边，格式为访问权限：144//请输入边，格式为访问权限：233//请输入边，格式为访问权限：317//请输入边，格式为访问权限：341//请输入边，格式为访问权限：415//请输入边，格式为访问权限：4312//测试最短第四个节点到其他节点的路径Dijkstra($graphArr,4);//5//7//10//0代码增加了很多，但是仔细看核心算法部分，这次是只嵌套了两层循环，时间复杂度一下子降到了O(N2)，比Floyd算法提高了很多。当然，它的场景也是有限的，就是只能逐个节点计算。好吧，让我们看看Dijkstra在做什么。我们还是用上面那个简单的图，研究从节点4到其他节点的算法执行过程。首先，我们将默认值从节点4初始化为所有其他节点。此时节点4到节点2没有直接路径，所以是无穷大，而到节点1是5，到节点3是12。然后将节点4标记为已访问，即book[4]=1进入核心算法，从头开始遍历该节点，这里是标记为i的下标，因为这是单源的最短路径，所以我们不需要看到自己的最短路径，只需要n-1次循环就可以开始第j层的循环，先判断当前节点是否被标记过，如果没有，再检查其值是否为最小值后最后循环完成，得到一条从节点4开始的权值最小的路径，将这条路径到达的节点标记为u，u下标标记的节点为访问节点，进入v循环。判断图中从u到v的节点是否无限大，如果不是，则判断从u到v的节点的权重值加上原来的dis[u]是否小于dis[v]中记录的权重，如果大于这个，如果小，更新dis[v]为从u到v的节点加上原来dis[u]的权重，重复比较，完成算法。对于节点4，dis发生了如下变化：首先，默认情况下dis=[5,9999999,12,0]第一次循环后，节点1完成查找，在v的循环中发现它可以从节点1到节点2和节点3并且比原来的值都小，所以dis=[5,7,11,0]经过第二次循环，节点2完成查找，本次循环找到节点2到节点3的距离更短，所以dis=[5,7,10,0]第三次循环后，节点3完成搜索，但没有找到更短的路径，dis=[5,7,10,0]你明白吗？如果你不明白，你自己试试看。无论是断点还是中间输出dis和book，都可以帮助我们更好的理解算法的每一步是如何执行的。从代码中可以看出，这个Dijkstra算法的时间复杂度是O(N2)，比Floyd快很多。图的两个最典型的应用和算法到此结束。当然，图表的内容可以远不止于此。比较典型的就是进度网络图之类的算法，在做一些项目管理系统的时候特别有用。当然，更深入的内容还有待研究《图论》。这远远超出了我的水平。希望有更多数学相关基础的同学可以继续深入学习。至于我呢，先去补数学吧！！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5。图/source/5.5图的应用：ShortestPath.php参考文档：《数据结构》第二版，闫伟民《数据结构》第2版，陈越《数据结构高分笔记》2020年版，天琴考研《啊哈！算法》各自媒体可搜索平台【硬核项目经理】