圖的應用：最短路徑
上篇文章的最小生成樹有沒有意猶未盡的感覺呀？不知道大家掌握得怎麼樣，是不是搞清楚了普里姆和克魯斯卡爾這兩種演算法的原理了呢？面試的時候如果你寫不出，至少得說出個大概來吧，當然，如果你是要考研的學生，那就要深入的理解並且記住整個演算法的程式碼了。
什麼是最短路徑
今天我們學習的是圖的應用中另外一個經典的問題，也就是 最短路徑 的問題。這個問題和最小生成樹是不同的，最小生成樹的要求是要連通所有的結點，並且走得是權值最小的那條路線。而最短路徑則是指的從某個頂點到另一個頂點中權值最小的那條路徑。這條路徑不一定是包含在最小生成樹中的，所以它們並沒有太大的連結。
從這張圖來看，我們從結點 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][j] 。這時，由於有最外層的k 存在，所以我們也知道如果i 從k 走再從k 到j 的長度，也就是[i][k] [k][i] 這段距離
很明顯，如果[i][k] [k][i] 的距離要比[i][j] 短的話，更新[i][j] 的值為[i][k] [k ][i]
內部的i 和j 迴圈完成後，第1 個結點做為媒介跳轉的遍歷也完成了，當前的矩陣中各個結點之間的權重已經是經過第1 個結點做為媒介之後的最短路徑了
但是呢，這並不準確，說不定我們可能經過i 、k1 、 k2 、 j 的路徑才是最短的，所以外層的k迴圈繼續遍歷並將第2 個結點當作媒介結點
迴圈往復直到所有結點都做過一次中間的媒介結點之後，我們就得到了一個最短路徑的矩陣圖，也就是我們上面測試程式碼中輸出的結果
我們就拿結點4 和結點3 來說明。我們定義 4 為 i ，結點 3 為 j 。
初始化时，[i][j] 为 12 ，这个没什么问题，单向图的那条带箭头的边的权值就是 12 。
然后当 k 为 1 时，也就是我们经过结点 1 来看路径有没有变短，这时 [i][k] 是 5 ，[k][j] 是 6 ，OK，路径变成 11 了，把 [i][j] 的值改成 11 。
同时，在 i 为 4 ，j 为 2 的情况下，他们两个的最短路径也在这次 k=1 的循环中被赋值为 7 。最开始 4 到 2 是没有直接的边的，现在在结点 1 的连接下，他们有了路径，也就是 [4][2] = [4][1] + [1][2] = 7 。
当 k 为 2 时，[i][j] 为 11 ，这时 [i][k] 就是上面说过的 [4][2] 。也就是 7 ，而 [k][j] 则是 3 ，路径又缩小了，[i][k] + [k][j] = 10 ，[i][j] 现在又变成了 10 。
循环继续，但已经没有比这条路径更小的值了，所以最后 [4][2] 的最短路径就是 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
登入後複製
推荐：《PHP视频教程》
以上是PHP資料結構之什麼是圖形應用中的最短路徑？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
