http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.1.png" alt="picture6.1" />
暑假，小哼準備去一些城市旅游。有些城市之間有公路，有些城市之間則沒有，如下圖。為了節(jié)省經(jīng)費以及方便計劃旅程，小哼希望在出發(fā)之前知道任意兩個城市之前的最短路程。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.2.png" alt="picture6.2" />
上圖中有 4 個城市 8 條公路，公路上的數(shù)字表示這條公路的長短。請注意這些公路是單向的。我們現(xiàn)在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題。
現(xiàn)在需要一個數(shù)據(jù)結(jié)構(gòu)來存儲圖的信息，我們?nèi)匀豢梢杂靡粋€ 4*4 的矩陣（二維數(shù)組 e）來存儲。比如 1 號城市到 2 號城市的路程為 2，則設(shè) e[1][2]的值為 2。2 號城市無法到達 4 號城市，則設(shè)置 e[2][4]的值為 ∞。另外此處約定一個城市自己是到自己的也是 0，例如 e[1][1]為 0，具體如下。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.3.png" alt="picture6.3" />
現(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)過第三個點時，這些城市之間最短路程就是初始路程，如下。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.4.png" alt="picture6.4" />
如現(xiàn)在只允許經(jīng)過 1 號頂點，求任意兩點之間的最短路程，應(yīng)該如何求呢？只需判斷 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)如下。
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if ( e[i][j] > e[i][1]+e[1][j] )
e[i][j] = e[i][1]+e[1][j];
}
}
在只允許經(jīng)過 1 號頂點的情況下，任意兩點之間的最短路程更新為：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.5.png" alt="picture6.5" />
通過上圖我們發(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號頂點
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
//經(jīng)過2號頂點
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
在只允許經(jīng)過 1 和 2 號頂點的情況下，任意兩點之間的最短路程更新為：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.6.png" alt="picture6.6" />
通過上圖得知，在相比只允許通過 1 號頂點進行中轉(zhuǎn)的情況下，這里允許通過 1 和 2 號頂點進行中轉(zhuǎn)，使得 e[1][3]和 e[4][3]的路程變得更短了。
同理，繼續(xù)在只允許經(jīng)過 1、2 和 3 號頂點進行中轉(zhuǎn)的情況下，求任意兩點之間的最短路程。任意兩點之間的最短路程更新為：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.7.png" alt="picture6.7" />
最后允許通過所有頂點作為中轉(zhuǎn)，任意兩點之間最終的最短路程為：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.8.png" alt="picture6.8" />
整個算法過程雖然說起來很麻煩，但是代碼實現(xiàn)卻非常簡單，核心代碼只有五行：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
這段代碼的基本思想就是：最開始只允許經(jīng)過 1 號頂點進行中轉(zhuǎn)，接下來只允許經(jīng)過 1 和 2 號頂點進行中轉(zhuǎn)……允許經(jīng)過 1~n 號所有頂點進行中轉(zhuǎn)，求任意兩點之間的最短路程。用一句話概括就是：從 i 號頂點到 j 號頂點只經(jīng)過前k號點的最短路程。其實這是一種“動態(tài)規(guī)劃”的思想，關(guān)于這個思想我們將在《啊哈！算法 2——偉大思維閃耀時》在做詳細的討論。下面給出這個算法的完整代碼：
#include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值
//讀入n和m，n表示頂點個數(shù)，m表示邊的條數(shù)
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//讀入邊
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshall算法核心語句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
//輸出最終的結(jié)果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
有一點需要注意的是：如何表示正無窮。我們通常將正無窮定義為 99999999，因為這樣即使兩個正無窮相加，其和仍然不超過 int 類型的范圍（C 語言 int 類型可以存儲的最大正整數(shù)是 2147483647）。在實際應(yīng)用中最好估計一下最短路徑的上限，只需要設(shè)置比它大一點既可以。例如有 100 條邊，每條邊不超過 100 的話，只需將正無窮設(shè)置為 10001 即可。如果你認為正無窮和其它值相加得到一個大于正無窮的數(shù)是不被允許的話，我們只需在比較的時候加兩個判斷條件就可以了，請注意下面代碼中帶有下劃線的語句。
//Floyd-Warshall算法核心語句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
上面代碼的輸入數(shù)據(jù)樣式為：
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
第一行兩個數(shù)為 n 和 m，n 表 示頂點個數(shù)，m 表示邊的條數(shù)。
接下來 m 行，每一行有三個數(shù) t1、t2 和 t3，表示頂點 t1 到頂點 t2 的路程是 t3。
得到最終結(jié)果如下：
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.9.png" alt="picture6.9" />
通過這種方法我們可以求出任意兩個點之間最短路徑。它的時間復(fù)雜度是 O(N3)。令人很震撼的是它竟然只有五行代碼，實現(xiàn)起來非常容易。正是因為它實現(xiàn)起來非常容易，如果時間復(fù)雜度要求不高，使用 Floyd-Warshall 來求指定兩點之間的最短路或者指定一個點到其余各個頂點的最短路徑也是可行的。當然也有更快的算法，請看下一節(jié)：Dijkstra 算法。
另外需要注意的是：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)回路”那么這個圖則沒有最短路。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/6.10.png" alt="picture6.10" />
此算法由 Robert W. Floyd（羅伯特·弗洛伊德）于 1962 年發(fā)表在“Communications of the ACM”上。同年 Stephen Warshall（史蒂芬·沃舍爾）也獨立發(fā)表了這個算法。Robert W．Floyd 這個牛人是朵奇葩，他原本在芝加哥大學讀的文學，但是因為當時美國經(jīng)濟不太景氣，找工作比較困難，無奈之下到西屋電氣公司當了一名計算機操作員，在 IBM650 機房值夜班，并由此開始了他的計算機生涯。此外他還和 J.W.J. Williams（威廉姆斯）于 1964 年共同發(fā)明了著名的堆排序算法 HEAPSORT。堆排序算法我們將在第七章學習。Robert W．Floyd 在 1978 年獲得了圖靈獎。
【一周一算法】算法 6：只有五行的 Floyd 最短路算法
http://bbs.ahalei.com/thread-4554-1-1.html
(出處: 啊哈磊_編程從這里起步)
掃碼關(guān)注鍍金池微信號
手機訂課，優(yōu)惠多多