上篇文章的最小生成樹有沒有意猶未盡的感覺呀？不知道大家掌握得怎么樣，是不是搞清楚了普里姆和克魯斯卡爾這兩種算法的原理了呢？面試的時(shí)候如果你寫不出，至少得說出個大概來吧，當(dāng)然，如果你是要考研的學(xué)生，那就要深入的理解并且記住整個算法的代碼了。
今天我們學(xué)習(xí)的是圖的應(yīng)用中另外一個經(jīng)典的問題，也就是 最短路徑 的問題。這個問題和最小生成樹是不同的，最小生成樹的要求是要連通所有的結(jié)點(diǎn)，并且走得是權(quán)值最小的那條路線。而最短路徑則是指的從某個頂點(diǎn)到另一個頂點(diǎn)中權(quán)值最小的那條路徑。這條路徑不一定是包含在最小生成樹中的，所以它們并沒有太大的聯(lián)系。
從這張圖來看，我們從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 2 的最短路徑是 2 ，這個很明顯。那么從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 3 呢？可不是直接的中間那個權(quán)值為 6 的路徑，而是走 1->2->3 這條路徑，也就是權(quán)值加起來為 5 的這條路徑。
然后我們再來看結(jié)點(diǎn) 3 ，它到結(jié)點(diǎn) 1 最短路徑應(yīng)該是走 3->4->1 這條路徑，也就是權(quán)值為 6 的這條路徑，而不是中間的那條直線的權(quán)值為 7 的路徑。
沒錯，這就是最短路徑的概念了。在最短路徑中，我們一般會解決單向圖的問題，但實(shí)際生活中呢？最典型的地圖相關(guān)的應(yīng)用其實(shí)是都是雙向圖的。不過這并不影響我們的學(xué)習(xí)，我們可以把這個示例圖中的結(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)然，這只是例子，大家在非高鐵的情況下肯定還是更多地會選擇起始站的火車來坐）。
首先，我們先說一個多源最短路徑的算法。那么什么叫做多源呢？
其實(shí)就是這一個算法就能夠得出所有結(jié)點(diǎn)到所有結(jié)點(diǎn)之間的最短路徑。沒錯，就這一個算法，不管哪個結(jié)點(diǎn)到哪個結(jié)點(diǎn)，它們之間的最短路徑都一次性算出來了。神奇嗎？不不不，更神奇的，而且你一會就會叫出 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;
}
}
// 請輸入結(jié)點(diǎn)數(shù)：4
// 請輸入邊數(shù)：8
// 請輸入邊，格式為 出 入 權(quán)：1 2 2
// 請輸入邊，格式為 出 入 權(quán)：1 3 6
// 請輸入邊，格式為 出 入 權(quán)：1 4 4
// 請輸入邊，格式為 出 入 權(quán)：2 3 3
// 請輸入邊，格式為 出 入 權(quán)：3 1 7
// 請輸入邊，格式為 出 入 權(quán)：3 4 1
// 請輸入邊，格式為 出 入 權(quán)：4 1 5
// 請輸入邊，格式為 出 入 權(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 。也就是說，原來的那個圖的鄰接矩陣成了這個最短路徑的矩陣。每一行代表每個結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短距離。
好吧，結(jié)果沒問題，那么代碼到底是寫得啥玩意？這個 k 是什么？別急，我們一步一步來看。
假設(shè)兩點(diǎn)之間的距離不是最短的，那么肯定是有另外一個點(diǎn)做為媒介進(jìn)行跳轉(zhuǎn)，由 i 點(diǎn)先跳到這個點(diǎn)然后再跳向 j 點(diǎn)，這樣的一條路徑是比直接的 i 到 j 要近的，我們就定義這個點(diǎn)為 k 點(diǎn)
但是我們不知道要走哪個結(jié)點(diǎn)呀，而且還有可能不只是一個 k ，或許我們從 i 到 j 要經(jīng)歷好多個 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 個結(jié)點(diǎn)做為媒介跳轉(zhuǎn)的遍歷也完成了，當(dāng)前的矩陣中各個結(jié)點(diǎn)之間的權(quán)重已經(jīng)是經(jīng)過第 1 個結(jié)點(diǎn)做為媒介之后的最短路徑了
但是呢，這并不準(zhǔn)確，說不定我們可能經(jīng)過 i 、k1 、 k2 、 j 的路徑才是最短的，所以外層的 k 循環(huán)繼續(xù)遍歷并將第 2 個結(jié)點(diǎn)作為媒介結(jié)點(diǎn)
循環(huán)往復(fù)直到所有結(jié)點(diǎn)都做過一次中間的媒介結(jié)點(diǎn)之后，我們就得到了一個最短路徑的矩陣圖，也就是我們上面測試代碼中輸出的結(jié)果
我們就拿結(jié)點(diǎn) 4 和結(jié)點(diǎn) 3 來說明。我們定義 4 為 i ，結(jié)點(diǎn) 3 為 j 。
初始化時(shí)，[i][j] 為 12 ，這個沒什么問題，單向圖的那條帶箭頭的邊的權(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 的情況下，他們兩個的最短路徑也在這次 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)前的最短路徑矩陣變成什么樣了。這樣畫一次之后，馬上就知道這個 Floyd 算法的核心奧秘所在了。
不得不說，前人的智慧真的很偉大吧，不過說是前人，其實(shí) Floyd 大佬在 1962 年才發(fā)表了這個算法，但這個算法的核心思想?yún)s是數(shù)學(xué)中的動態(tài)規(guī)劃的思想。所以說，算法和數(shù)學(xué)是沒法分家的，各位大佬哪個不是數(shù)學(xué)界的一把手呢。
說完了多源最短路徑，我們再講一個鼎鼎大名的單源最短路徑的算法。雖說上面的多源很牛X，但是它的時(shí)間復(fù)雜度也就是時(shí)間效率也確實(shí)是太差了，沒看錯的話三個 N 次的循環(huán)嵌套就是 O(N3)。如果數(shù)據(jù)稍微多一點(diǎn)的話基本就可以從 Oh!My God! 變成 Oh!FxxK! 了。而且大多數(shù)情況下，我們的需求都會是固定的求從某一點(diǎn)到另一點(diǎn)的最短路徑問題，也就是單源最短路徑問題。這時(shí)，就可以使用這種效率稍微好一點(diǎn)的算法來快速地解決了。
// origin 表示源點(diǎn)，也就是我們要看哪個結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短路徑
function Dijkstra($graphArr, $origin)
{
$n = count($graphArr);
$dis = []; // 記錄最小值
$book = []; // 記錄結(jié)點(diǎn)是否訪問過
// 初始化源點(diǎn)到每個點(diǎn)的權(quán)值
for ($i = 1; $i <= $n; $i++) {
$dis[$i] = $graphArr[$origin][$i]; // 源點(diǎn)到其它點(diǎn)的默認(rèn)權(quán)值
$book[$i] = 0; // 所有結(jié)點(diǎn)都沒訪問過
}
$book[$origin] = 1; // 源點(diǎn)自身標(biāo)記為已訪問
// 核心算法
for ($i = 1; $i <= $n - 1; $i++) {
$min = INFINITY;
// 找到離目標(biāo)結(jié)點(diǎn)最近的結(jié)點(diǎn)
for ($j = 1; $j <= $n; $j++) {
// 如果結(jié)點(diǎn)沒有被訪問過，并且當(dāng)前結(jié)點(diǎn)的權(quán)值小于 min 值
if ($book[$j] == 0 && $dis[$j] < $min) {
$min = $dis[$j]; // min 修改為當(dāng)前這個節(jié)點(diǎn)的路徑值
$u = $j; // 變量 u 變?yōu)楫?dāng)前這個結(jié)點(diǎn)
}
// 遍歷完所有結(jié)點(diǎn)，u 就是最近的那個頂點(diǎn)
}
$book[$u] = 1; // 標(biāo)記 u 為已訪問
for ($v = 1; $v <= $n; $v++) {
// 如果 [u][v] 頂點(diǎn)小于無窮
if ($graphArr[$u][$v] < INFINITY) {
// 如果當(dāng)前 dis[v] 中的權(quán)值大于 dis[u]+g[u][v]
if ($dis[$v] > $dis[$u] + $graphArr[$u][$v]) {
// 將當(dāng)前的 dis[v] 賦值為 dis[u]+g[u][v]
$dis[$v] = $dis[$u] + $graphArr[$u][$v];
}
}
}
// 最近的結(jié)點(diǎn)完成，繼續(xù)下一個最近的結(jié)點(diǎn)
}
for ($i = 1; $i <= $n; $i++) {
echo $dis[$i], PHP_EOL;
}
}
// 請輸入結(jié)點(diǎn)數(shù)：4
// 請輸入邊數(shù)：8
// 請輸入邊，格式為 出 入 權(quán)：1 2 2
// 請輸入邊，格式為 出 入 權(quán)：1 3 6
// 請輸入邊，格式為 出 入 權(quán)：1 4 4
// 請輸入邊，格式為 出 入 權(quán)：2 3 3
// 請輸入邊，格式為 出 入 權(quán)：3 1 7
// 請輸入邊，格式為 出 入 權(quán)：3 4 1
// 請輸入邊，格式為 出 入 權(quán)：4 1 5
// 請輸入邊，格式為 出 入 權(quán)：4 3 12
// 測試第四個結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短路徑
Dijkstra($graphArr, 4);
// 5
// 7
// 10
// 0
代碼一下增加了不少吧，不過仔細(xì)看一下核心的算法部分，這次只是兩層循環(huán)的嵌套了，時(shí)間復(fù)雜度一下子就降到了 O(N2) ，這一下就比 Floyd 算法提升了很多。當(dāng)然，它的場景也是有限的，那就是只能一個結(jié)點(diǎn)一個結(jié)點(diǎn)的計(jì)算。
好了，我們還是來看一下 Dijkstra 到底在干嘛吧。我們依然是使用上面那個簡單的圖，并且還是研究結(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)完成后獲得一個從結(jié)點(diǎn) 4 出發(fā)的權(quán)值最小的路徑，并將這條路徑到達(dá)的結(jié)點(diǎn)下標(biāo)記為 u ，標(biāo)記 u 下標(biāo)的這個結(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)值，如果比這個小的話，更新 dis[v] 為 u 到 v 的結(jié)點(diǎn)加上原來的 dis[u] 的權(quán)值
循環(huán)重復(fù)地進(jìn)行比較完成算法
對于結(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 ，都能夠幫助我們更好地理解這個算法的每一步是如何執(zhí)行的。從代碼中就可以看出來，這個 Dijkstra 算法的時(shí)間復(fù)雜度是 O(N2) ，這可比 Floyd 快了不少了吧。
關(guān)于圖的兩種最典型的應(yīng)用及算法就到這里結(jié)束了。當(dāng)然，圖的內(nèi)容可遠(yuǎn)不止這些，比較典型的還是進(jìn)度網(wǎng)絡(luò)圖等的算法，特別是做一些項(xiàng)目管理類的系統(tǒng)時(shí)會非常有用。當(dāng)然，更高深的內(nèi)容就要去研究《圖論》了。這個可就遠(yuǎn)超我的水平了，希望有更多數(shù)學(xué)相關(guān)基礎(chǔ)的同學(xué)能夠繼續(xù)深入研究。而我嘛，先去惡補(bǔ)下數(shù)學(xué)吧??！
測試代碼：
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版，天勤考研
《啊哈！算法》
