共计 4931 个字符，预计需要花费 13 分钟才能阅读完成。
上篇文章的最小生成树有没有意犹未尽的感觉呀？不晓得大家把握得怎么样，是不是搞清楚了普里姆和克鲁斯卡尔这两种算法的原理了呢？面试的时候如果你写不出，至多得说出个大略来吧，当然，如果你是要考研的学生，那就要深刻的了解并且记住整个算法的代码了。
什么是最短门路
明天咱们学习的是图的利用中另外一个经典的问题，也就是 最短门路 的问题。这个问题和最小生成树是不同的，最小生成树的要求是要连通所有的结点，并且走得是权值最小的那条路线。而最短门路则是指的从某个顶点到另一个顶点中权值最小的那条门路。这条门路不肯定是蕴含在最小生成树中的，所以它们并没有太大的分割。
从这张图来看，咱们从结点 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 算法
首先，咱们先说一个多源最短门路的算法。那么什么叫做多源呢？
其实就是这一个算法就可能得出所有结点到所有结点之间的最短门路。没错，就这一个算法，不论哪个结点到哪个结点，它们之间的最短门路都一次性算进去了。神奇吗？不不不，更神奇的，而且你一会就会叫出 Oh!My God! 的是它的外围代码，只有五行！！
function 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 的门路变短，那么将 i 到 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], ' ';
}
echo PHP_EOL;
}
}
// 请输出结点数：4
// 请输出边数：8
// 请输出边，格局为 出 入 权：1 2 2
// 请输出边，格局为 出 入 权：1 3 6
// 请输出边，格局为 出 入 权：1 4 4
// 请输出边，格局为 出 入 权：2 3 3
// 请输出边，格局为 出 入 权：3 1 7
// 请输出边，格局为 出 入 权：3 4 1
// 请输出边，格局为 出 入 权：4 1 5
// 请输出边，格局为 出 入 权：4 3 12
// 0 2 5 4
// 9 0 3 4
// 6 8 0 1
// 5 7 10 0 咱们能够先验证下后果，就是正文中最初输入的矩阵。结点 1 到结点 2、3、4 的最短距离为 2、5、4。结点 3 到结点 1、2、4 的最短距离为 6、8、1。也就是说，原来的那个图的邻接矩阵成了这个最短门路的矩阵。每一行代表每个结点到其它结点的最短距离。
好吧，后果没问题，那么代码到底是写得啥玩意？这个 k 是什么？别急，咱们一步一步来看。
- 假如两点之间的间隔不是最短的，那么必定是有另外一个点做为媒介进行跳转，由 i 点先跳到这个点而后再跳向 j 点，这样的一条门路是比间接的 i 到 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 循环实现后，第 1 个结点做为媒介跳转的遍历也实现了，以后的矩阵中各个结点之间的权重曾经是通过第 1 个结点做为媒介之后的最短门路了
- 然而呢，这并不精确，说不定咱们可能通过 i、k1、k2、j 的门路才是最短的，所以外层的 k 循环持续遍历并将第 2 个结点作为媒介结点
- 周而复始直到所有结点都做过一次两头的媒介结点之后，咱们就失去了一个最短门路的矩阵图，也就是咱们下面测试代码中输入的后果
咱们就拿结点 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=1 的循环中被赋值为 7。最开始 4 到 2 是没有间接的边的，当初在结点 1 的连贯下，他们有了门路，也就是 4 = 4 + 1 = 7。
当 k 为 2 时，i 为 11，这时 i 就是下面说过的 4。也就是 7，而 k 则是 3，门路又放大了，i + k = 10，i 当初又变成了 10。
循环持续，但曾经没有比这条门路更小的值了，所以最初 4 的最短门路就是 10。
看着晕吗？拿出笔来在纸上或者本子上本人画画，每一步的 k 都去画一下以后的最短门路矩阵变成什么样了。这样画一次之后，马上就晓得这个 Floyd 算法的外围神秘所在了。
不得不说，前人的智慧真的很平凡吧，不过说是前人，其实 Floyd 大佬在 1962 年才发表了这个算法，但这个算法的核心思想却是数学中的动静布局的思维。所以说，算法和数学是没法分家的，各位大佬哪个不是数学界的一把手呢。
单源最短门路 Dijkstra 算法
说完了多源最短门路，咱们再讲一个鼎鼎大名的单源最短门路的算法。虽说下面的多源很牛 X，然而它的工夫复杂度也就是工夫效率也的确是太差了，没看错的话三个 N 次的循环嵌套就是 O(N3)。如果数据略微多一点的话根本就能够从 Oh!My God! 变成 Oh!FxxK! 了。而且大多数状况下，咱们的需要都会是固定的求从某一点到另一点的最短门路问题，也就是单源最短门路问题。这时，就能够应用这种效率略微好一点的算法来疾速地解决了。
// origin 示意源点，也就是咱们要看哪个结点到其它结点的最短门路
function Dijkstra($graphArr, $origin)
{$n = count($graphArr);
$dis = []; // 记录最小值
$book = []; // 记录结点是否拜访过
// 初始化源点到每个点的权值
for ($i = 1; $i <= $n; $i++) {$dis[$i] = $graphArr[$origin][$i]; // 源点到其它点的默认权值
$book[$i] = 0; // 所有结点都没拜访过
}
$book[$origin] = 1; // 源点本身标记为已拜访
// 外围算法
for ($i = 1; $i <= $n - 1; $i++) {
$min = INFINITY;
// 找到离指标结点最近的结点
for ($j = 1; $j <= $n; $j++) {
// 如果结点没有被拜访过，并且以后结点的权值小于 min 值
if ($book[$j] == 0 && $dis[$j] < $min) {$min = $dis[$j]; // min 批改为以后这个节点的门路值
$u = $j; // 变量 u 变为以后这个结点
}
// 遍历完所有结点，u 就是最近的那个顶点
}
$book[$u] = 1; // 标记 u 为已拜访
for ($v = 1; $v <= $n; $v++) {// 如果 [u][v] 顶点小于无穷
if ($graphArr[$u][$v] < INFINITY) {// 如果以后 dis[v] 中的权值大于 dis[u]+g[u][v]
if ($dis[$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
// 请输出边，格局为 出 入 权：1 2 2
// 请输出边，格局为 出 入 权：1 3 6
// 请输出边，格局为 出 入 权：1 4 4
// 请输出边，格局为 出 入 权：2 3 3
// 请输出边，格局为 出 入 权：3 1 7
// 请输出边，格局为 出 入 权：3 4 1
// 请输出边，格局为 出 入 权：4 1 5
// 请输出边，格局为 出 入 权：4 3 12
// 测试第四个结点到其它结点的最短门路
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 图的利用：最短门路.php
参考文档：
《数据结构》第二版，严蔚敏
《数据结构》第二版，陈越
《数据结构高分笔记》2020 版，天勤考研
《啊哈！算法》
各自媒体平台均可搜寻【硬核项目经理】