圖的應(yīng)用：最短路徑

上篇文章的最小生成樹有沒有意猶未盡的感覺呀？不知道大家掌握得怎么樣，是不是搞清楚了普里姆和克魯斯卡爾這兩種算法的原理了呢？面試的時(shí)候如果你寫不出，至少得說出個(gè)大概來吧，當(dāng)然，如果你是要考研的學(xué)生，那就要深入的理解并且記住整個(gè)算法的代碼了。

什么是最短路徑

今天我們學(xué)習(xí)的是圖的應(yīng)用中另外一個(gè)經(jīng)典的問題，也就是 最短路徑 的問題。這個(gè)問題和最小生成樹是不同的，最小生成樹的要求是要連通所有的結(jié)點(diǎn)，并且走得是權(quán)值最小的那條路線。而最短路徑則是指的從某個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)中權(quán)值最小的那條路徑。這條路徑不一定是包含在最小生成樹中的，所以它們并沒有太大的聯(lián)系。

從這張圖來看，我們從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 2 的最短路徑是 2 ，這個(gè)很明顯。那么從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 3 呢？可不是直接的中間那個(gè)權(quán)值為 6 的路徑，而是走 1->2->3 這條路徑，也就是權(quán)值加起來為 5 的這條路徑。

然后我們?cè)賮砜唇Y(jié)點(diǎn) 3 ，它到結(jié)點(diǎn) 1 最短路徑應(yīng)該是走 3->4->1 這條路徑，也就是權(quán)值為 6 的這條路徑，而不是中間的那條直線的權(quán)值為 7 的路徑。

沒錯(cuò)，這就是最短路徑的概念了。在最短路徑中，我們一般會(huì)解決單向圖的問題，但實(shí)際生活中呢？最典型的地圖相關(guān)的應(yīng)用其實(shí)是都是雙向圖的。不過這并不影響我們的學(xué)習(xí)，我們可以把這個(gè)示例圖中的結(jié)點(diǎn)看成是城市火車站點(diǎn)，就算是連接結(jié)點(diǎn) 1 和結(jié)點(diǎn) 3 的火車線路，也不一定來去的時(shí)間都是相同的。比如說從長沙到北京的 Z2 次火車全部運(yùn)行時(shí)間為14小時(shí)42分，而回來的 Z1 次則是14小時(shí)10分。那么我們是否可以選擇其它的火車，比如有趟火車從長沙到石家莊可能只需要8小時(shí)，然后從石家莊到北京只需要2小時(shí)，這樣我們選擇這條線路的總時(shí)間就只需要10小時(shí)了（當(dāng)然，這只是例子，大家在非高鐵的情況下肯定還是更多地會(huì)選擇起始站的火車來坐）。

多源最短路徑 Floyd 算法

首先，我們先說一個(gè)多源最短路徑的算法。那么什么叫做多源呢？

其實(shí)就是這一個(gè)算法就能夠得出所有結(jié)點(diǎn)到所有結(jié)點(diǎn)之間的最短路徑。沒錯(cuò)，就這一個(gè)算法，不管哪個(gè)結(jié)點(diǎn)到哪個(gè)結(jié)點(diǎn)，它們之間的最短路徑都一次性算出來了。神奇嗎？不不不，更神奇的，而且你一會(huì)就會(huì)叫出 Oh!My God! 的是它的核心代碼，只有五行?。?/p>function Floyd($graphArr){
    $n = count($graphArr);
    
    for($k = 1;$k<=$n;$k++){ // 設(shè) k 為經(jīng)過的結(jié)點(diǎn)
        for($i = 1;$i<=$n;$i++){
            for($j = 1;$j<=$n;$j++){
                // 如果經(jīng)過 k 結(jié)點(diǎn) 能使 i 到 j 的路徑變短，那么將 i 到 j 之間的更新為通過 k 中轉(zhuǎn)之后的結(jié)果 
                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;
    }
}
// 請(qǐng)輸入結(jié)點(diǎn)數(shù)：4
// 請(qǐng)輸入邊數(shù)：8
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：1 2 2
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：1 3 6
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：1 4 4
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：2 3 3
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：3 1 7
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：3 4 1
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：4 1 5
// 請(qǐng)輸入邊，格式為 出 入 權(quán)：4 3 12
// 0 2 5 4 
// 9 0 3 4 
// 6 8 0 1 
// 5 7 10 0 


我們可以先驗(yàn)證下結(jié)果，就是注釋中最后輸出的矩陣。結(jié)點(diǎn) 1 到結(jié)點(diǎn) 2、3、4的最短距離為 2 、5 、4 。結(jié)點(diǎn) 3 到結(jié)點(diǎn) 1 、2 、4 的最短距離為 6 、8 、1 。也就是說，原來的那個(gè)圖的鄰接矩陣成了這個(gè)最短路徑的矩陣。每一行代表每個(gè)結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短距離。

好吧，結(jié)果沒問題，那么代碼到底是寫得啥玩意？這個(gè) k 是什么？別急，我們一步一步來看。

• 假設(shè)兩點(diǎn)之間的距離不是最短的，那么肯定是有另外一個(gè)點(diǎn)做為媒介進(jìn)行跳轉(zhuǎn)，由 i 點(diǎn)先跳到這個(gè)點(diǎn)然后再跳向 j 點(diǎn)，這樣的一條路徑是比直接的 i 到 j 要近的，我們就定義這個(gè)點(diǎn)為 k 點(diǎn)

• 但是我們不知道要走哪個(gè)結(jié)點(diǎn)呀，而且還有可能不只是一個(gè) k ，或許我們從 i 到 j 要經(jīng)歷好多個(gè) k ，這時(shí)候，我們就從 k 開始遍歷，也就是第一層循環(huán)

• 在第一層循環(huán)下，進(jìn)行我們正常的 i 和 j 的遍歷循環(huán)，獲得 i 直接到 j 的長度，也就是 [i][j] 。這時(shí)，由于有最外層的 k 存在，所以我們也知道了如果 i 從 k 走再從 k 到 j 的長度，也就是 [i][k] + [k][i] 這段距離

• 很明顯，如果 [i][k] + [k][i] 的距離要比 [i][j] 短的話，更新 [i][j] 的值為 [i][k] + [k][i]

• 內(nèi)部的 i 和 j 循環(huán)完成后，第 1 個(gè)結(jié)點(diǎn)做為媒介跳轉(zhuǎn)的遍歷也完成了，當(dāng)前的矩陣中各個(gè)結(jié)點(diǎn)之間的權(quán)重已經(jīng)是經(jīng)過第 1 個(gè)結(jié)點(diǎn)做為媒介之后的最短路徑了

• 但是呢，這并不準(zhǔn)確，說不定我們可能經(jīng)過 i 、k1 、 k2 、 j 的路徑才是最短的，所以外層的 k 循環(huán)繼續(xù)遍歷并將第 2 個(gè)結(jié)點(diǎn)作為媒介結(jié)點(diǎn)

• 循環(huán)往復(fù)直到所有結(jié)點(diǎn)都做過一次中間的媒介結(jié)點(diǎn)之后，我們就得到了一個(gè)最短路徑的矩陣圖，也就是我們上面測(cè)試代碼中輸出的結(jié)果

我們就拿結(jié)點(diǎn) 4 和結(jié)點(diǎn) 3 來說明。我們定義 4 為 i ，結(jié)點(diǎn) 3 為 j 。

初始化時(shí)，[i][j] 為 12 ，這個(gè)沒什么問題，單向圖的那條帶箭頭的邊的權(quán)值就是 12 。

然后當(dāng) k 為 1 時(shí)，也就是我們經(jīng)過結(jié)點(diǎn) 1 來看路徑有沒有變短，這時(shí) [i][k] 是 5 ，[k][j] 是 6 ，OK，路徑變成 11 了，把 [i][j] 的值改成 11 。

同時(shí)，在 i 為 4 ，j 為 2 的情況下，他們兩個(gè)的最短路徑也在這次 k=1 的循環(huán)中被賦值為 7 。最開始 4 到 2 是沒有直接的邊的，現(xiàn)在在結(jié)點(diǎn) 1 的連接下，他們有了路徑，也就是 [4][2] = [4][1] + [1][2] = 7 。

當(dāng) k 為 2 時(shí)，[i][j] 為 11 ，這時(shí) [i][k] 就是上面說過的 [4][2] 。也就是 7 ，而 [k][j] 則是 3 ，路徑又縮小了，[i][k] + [k][j] = 10 ，[i][j] 現(xiàn)在又變成了 10 。

循環(huán)繼續(xù)，但已經(jīng)沒有比這條路徑更小的值了，所以最后 [4][2] 的最短路徑就是 10 。

看著暈嗎？拿出筆來在紙上或者本子上自己畫畫，每一步的 k 都去畫一下當(dāng)前的最短路徑矩陣變成什么樣了。這樣畫一次之后，馬上就知道這個(gè) Floyd 算法的核心奧秘所在了。

不得不說，前人的智慧真的很偉大吧，不過說是前人，其實(shí) Floyd 大佬在 1962 年才發(fā)表了這個(gè)算法，但這個(gè)算法的核心思想?yún)s是數(shù)學(xué)中的動(dòng)態(tài)規(guī)劃的思想。所以說，算法和數(shù)學(xué)是沒法分家的，各位大佬哪個(gè)不是數(shù)學(xué)界的一把手呢。

單源最短路徑 Dijkstra 算法

說完了多源最短路徑，我們?cè)僦v一個(gè)鼎鼎大名的單源最短路徑的算法。雖說上面的多源很牛X，但是它的時(shí)間復(fù)雜度也就是時(shí)間效率也確實(shí)是太差了，沒看錯(cuò)的話三個(gè) N 次的循環(huán)嵌套就是 O(N³)。如果數(shù)據(jù)稍微多一點(diǎn)的話基本就可以從 Oh!My God! 變成 Oh!FxxK! 了。而且大多數(shù)情況下，我們的需求都會(huì)是固定的求從某一點(diǎn)到另一點(diǎn)的最短路徑問題，也就是單源最短路徑問題。這時(shí)，就可以使用這種效率稍微好一點(diǎn)的算法來快速地解決了。

代碼一下增加了不少吧，不過仔細(xì)看一下核心的算法部分，這次只是兩層循環(huán)的嵌套了，時(shí)間復(fù)雜度一下子就降到了 O(N²) ，這一下就比 Floyd 算法提升了很多。當(dāng)然，它的場(chǎng)景也是有限的，那就是只能一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的計(jì)算。

好了，我們還是來看一下 Dijkstra 到底在干嘛吧。我們依然是使用上面那個(gè)簡單的圖，并且還是研究結(jié)點(diǎn) 4 到其它結(jié)點(diǎn)的算法執(zhí)行情況。

• 首先，我們初始化結(jié)點(diǎn) 4 到其他所有結(jié)點(diǎn)的默認(rèn)值，這時(shí)結(jié)點(diǎn) 4 到結(jié)點(diǎn) 2 是沒有直接路徑的，所以是無窮大，而到結(jié)點(diǎn) 1 是 5，到結(jié)點(diǎn) 3 是 12 。

• 然后將結(jié)點(diǎn) 4 標(biāo)記為已訪問，也就是 book[4] = 1

• 進(jìn)入核心算法，從頭開始遍歷結(jié)點(diǎn)，這里是標(biāo)記為 i 下標(biāo)，因?yàn)檫@里是單源的最短路徑，所以我們不需要再看自己到自己的最短路徑了，只需要 n-1 次循環(huán)就可以了

• 開始 j 層的循環(huán)，先判斷當(dāng)前的結(jié)點(diǎn)是否已經(jīng)被標(biāo)記過，沒有被標(biāo)記過的話再看它的值是否是最小的，最后循環(huán)完成后獲得一個(gè)從結(jié)點(diǎn) 4 出發(fā)的權(quán)值最小的路徑，并將這條路徑到達(dá)的結(jié)點(diǎn)下標(biāo)記為 u ，標(biāo)記 u 下標(biāo)的這個(gè)結(jié)點(diǎn)為已訪問結(jié)點(diǎn)

• 進(jìn)入 v 循環(huán)，判斷圖中 u 到 v 的結(jié)點(diǎn)是否是無窮，如果不是的話再判斷 u 到 v 的結(jié)點(diǎn)加上原來的 dis[u] 的權(quán)值是否小于 dis[v] 中記錄的權(quán)值，如果比這個(gè)小的話，更新 dis[v] 為 u 到 v 的結(jié)點(diǎn)加上原來的 dis[u] 的權(quán)值

• 循環(huán)重復(fù)地進(jìn)行比較完成算法

對(duì)于結(jié)點(diǎn) 4 來說，dis 經(jīng)歷了如下的變化：

• 首先，默認(rèn)情況下 dis = [5, 9999999, 12, 0]

• 第一次循環(huán)后，結(jié)點(diǎn)1 完成查找，并在 v 的循環(huán)中發(fā)現(xiàn)了可以從結(jié)點(diǎn)1 到結(jié)點(diǎn)2 和結(jié)點(diǎn)3 而且比原來的值都要小 ，于是 dis = [5, 7, 11, 0]

• 第二次循環(huán)后，結(jié)點(diǎn)2 完成查找，這次循環(huán)發(fā)現(xiàn)從結(jié)點(diǎn)2 到結(jié)點(diǎn)3 的距離更短，于是 dis = [5, 7, 10, 0]

• 第三次循環(huán)后，結(jié)點(diǎn)3 完成查找，沒有發(fā)現(xiàn)更短的路徑，dis = [5, 7, 10, 0]

看明白了嗎？不明白的話自己試試吧，不管是斷點(diǎn)還是在中間輸出一下 dis 和 book ，都能夠幫助我們更好地理解這個(gè)算法的每一步是如何執(zhí)行的。從代碼中就可以看出來，這個(gè) Dijkstra 算法的時(shí)間復(fù)雜度是 O(N²) ，這可比 Floyd 快了不少了吧。

總結(jié)

關(guān)于圖的兩種最典型的應(yīng)用及算法就到這里結(jié)束了。當(dāng)然，圖的內(nèi)容可遠(yuǎn)不止這些，比較典型的還是進(jìn)度網(wǎng)絡(luò)圖等的算法，特別是做一些項(xiàng)目管理類的系統(tǒng)時(shí)會(huì)非常有用。當(dāng)然，更高深的內(nèi)容就要去研究《圖論》了。這個(gè)可就遠(yuǎn)超我的水平了，希望有更多數(shù)學(xué)相關(guān)基礎(chǔ)的同學(xué)能夠繼續(xù)深入研究。而我嘛，先去惡補(bǔ)下數(shù)學(xué)吧！！

測(cè)試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.圖/source/5.5圖的應(yīng)用：最短路徑.php

參考文檔：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研

《啊哈！算法》