暑假，小哼準備去一些城市旅游。有些城市之間有公路，有些城市之間則沒有，如下圖。為了節(jié)省經(jīng)費以及方便計劃旅程，小哼希望在出發(fā)之前知道任意兩個城市之前的最短路程。

上圖中有4個城市8條公路，公路上的數(shù)字表示這條公路的長短。請注意這些公路是單向的。我們現(xiàn)在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題。

現(xiàn)在需要一個數(shù)據(jù)結(jié)構(gòu)來存儲圖的信息，我們?nèi)匀豢梢杂靡粋€4*4的矩陣(二維數(shù)組e)來存儲。比如1號城市到2號城市的路程為2，則設e[1][2]的值為2。2號城市無法到達4號城市，則設置e[2][4]的值為∞。另外此處約定一個城市自己是到自己的也是0，例如e[1][1]為0，具體如下。

現(xiàn)在回到問題：如何求任意兩點之間最短路徑呢？通過之前的學習我們知道通過深度或廣度優(yōu)先搜索可以求出兩點之間的最短路徑。所以進行n2遍深度或廣度優(yōu)先搜索，即對每兩個點都進行一次深度或廣度優(yōu)先搜索，便可以求得任意兩點之間的最短路徑。可是還有沒有別的方法呢？

我們來想一想，根據(jù)我們以往的經(jīng)驗，如果要讓任意兩點(例如從頂點a點到頂點b)之間的路程變短，只能引入第三個點(頂點k)，并通過這個頂點k中轉(zhuǎn)即a->k->b，才可能縮短原來從頂點a點到頂點b的路程。那么這個中轉(zhuǎn)的頂點k是1~n中的哪個點呢？甚至有時候不只通過一個點，而是經(jīng)過兩個點或者更多點中轉(zhuǎn)會更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上圖中從4號城市到3號城市(4->3)的路程e[4][3]原本是12。如果只通過1號城市中轉(zhuǎn)(4->1->3)，路程將縮短為11(e[4][1]+e[1][3]=5+6=11)。其實1號城市到3號城市也可以通過2號城市中轉(zhuǎn)，使得1號到3號城市的路程縮短為5(e[1][2]+e[2][3]=2+3=5)。所以如果同時經(jīng)過1號和2號兩個城市中轉(zhuǎn)的話，從4號城市到3號城市的路程會進一步縮短為10。通過這個的例子，我們發(fā)現(xiàn)每個頂點都有可能使得另外兩個頂點之間的路程變短。好，下面我們將這個問題一般化。

當任意兩點之間不允許經(jīng)過第三個點時，這些城市之間最短路程就是初始路程，如下。

假如現(xiàn)在只允許經(jīng)過1號頂點，求任意兩點之間的最短路程，應該如何求呢？只需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i號頂點到j號頂點之間的路程。e[i][1]+e[1][j]表示的是從i號頂點先到1號頂點，再從1號頂點到j號頂點的路程之和。其中i是1~n循環(huán)，j也是1~n循環(huán)，代碼實現(xiàn)如下。

在只允許經(jīng)過1號頂點的情況下，任意兩點之間的最短路程更新為：

通過上圖我們發(fā)現(xiàn)：在只通過1號頂點中轉(zhuǎn)的情況下，3號頂點到2號頂點(e[3][2])、4號頂點到2號頂點(e[4][2])以及4號頂點到3號頂點(e[4][3])的路程都變短了。

接下來繼續(xù)求在只允許經(jīng)過1和2號兩個頂點的情況下任意兩點之間的最短路程。如何做呢？我們需要在只允許經(jīng)過1號頂點時任意兩點的最短路程的結(jié)果下，再判斷如果經(jīng)過2號頂點是否可以使得i號頂點到j號頂點之間的路程變得更短。即判斷e[i][2]+e[2][j]是否比e[i][j]要小，代碼實現(xiàn)為如下。

在只允許經(jīng)過1和2號頂點的情況下，任意兩點之間的最短路程更新為：

通過上圖得知，在相比只允許通過1號頂點進行中轉(zhuǎn)的情況下，這里允許通過1和2號頂點進行中轉(zhuǎn)，使得e[1][3]和e[4][3]的路程變得更短了。

同理，繼續(xù)在只允許經(jīng)過1、2和3號頂點進行中轉(zhuǎn)的情況下，求任意兩點之間的最短路程。任意兩點之間的最短路程更新為：

最后允許通過所有頂點作為中轉(zhuǎn)，任意兩點之間最終的最短路程為：

整個算法過程雖然說起來很麻煩，但是代碼實現(xiàn)卻非常簡單，核心代碼只有五行：

這段代碼的基本思想就是：最開始只允許經(jīng)過1號頂點進行中轉(zhuǎn)，接下來只允許經(jīng)過1和2號頂點進行中轉(zhuǎn)……允許經(jīng)過1~n號所有頂點進行中轉(zhuǎn)，求任意兩點之間的最短路程。用一句話概括就是：從i號頂點到j號頂點只經(jīng)過前k號點的最短路程。

另外需要注意的是：Floyd-Warshall算法不能解決帶有“負權(quán)回路”(或者叫“負權(quán)環(huán)”)的圖，因為帶有“負權(quán)回路”的圖沒有最短路。例如下面這個圖就不存在1號頂點到3號頂點的最短路徑。因為1->2->3->1->2->3->…->1->2->3這樣路徑中，每繞一次1->-2>3這樣的環(huán)，最短路就會減少1，永遠找不到最短路。其實如果一個圖中帶有“負權(quán)回路”那么這個圖則沒有最短路。

總結(jié)

以上是生活随笔為你收集整理的判断有向图g中顶点i到顶点j是否有路径_号称图的最短路径算法--Floyd算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。