我們時常會面臨著對路徑選擇的決策問題。例如在北京、上海、廣州等城市，因其城市面積較大，乘地鐵或公交都要考慮從A點到B點，如何換乘到達？
現(xiàn)實中，每個人需求不同，選擇方案就不盡相同。有人為了省錢，它需要的是路程最短（定價以路程長短為標準），但可能由于線路班次少，換乘站間距離長等原因并不省時間；而另一些人，為了要趕飛機火車或者早晨上班不遲到，他最大的需求是總時間要短；還有一類人，如老人行動不便，或者上班族下班，忙碌一天累得要死，他們都不想多走路，哪怕車子繞遠路耗時長也無所謂，關鍵是換乘要少，這樣可以在車上好好休息一下（有些線路方案換乘兩次比換乘三四次耗時還長）。這些都是老百姓的需求，簡單的圖形可以靠人的經(jīng)驗和感覺，但復雜的道路或地鐵網(wǎng)就需要計算機通過算法計算來提供最佳的方案。我們今天就要來研究關于圖的最短路徑的問題。
在網(wǎng)圖和非網(wǎng)圖中，最短路徑的含義是不同的。由于非網(wǎng)圖它沒有邊上的權值，所謂的最短路徑，其實就是指兩頂點之間經(jīng)過的邊數(shù)最少的路徑；而對于網(wǎng)圖來說，最短路徑，是指兩頂點之間經(jīng)過的邊上權值之和最少的路徑，并且我們稱路徑上的第一個頂點是源點，最后一個頂點是終點。顯然，我們研究網(wǎng)圖更有實際意義，就地圖來說，距離就是兩頂點間的權值之和。而非網(wǎng)圖完全可以理解為所有的邊的權值都為1的網(wǎng)。
我們要講解兩種求最短路徑的算法。先來講第一種，從某個源點到其余各頂點的最短路徑問題。
迪杰斯特拉（Dijkstra）算法
這是一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。它的思路大體是這樣的。
比如說要求下圖中頂點v0到頂點v1的最短距離，沒有比這更簡單的了，答案就是1，路徑就是直接v0連線到v1。
由于頂點v1還與v2、v3、v4連線，所以此時我們同時求得了v0→v1→v2=1+3=4，v0→v1→ v3=1+7=8，v0→v1→v4=1+5=6。
現(xiàn)在，我問v0到v2的最短距離，如果你不假思索地說是5，那就犯錯了。因為邊上都有權值，剛才已經(jīng)有v0→v1→v2的結果是4，比5還要小1個單位，它才是最短距離，如下圖所示。
由于頂點v2還與v4、v5連線，所以此時我們同時求得了v0→v2→v4其實就是v0→v1→v2→v4=4+1=5，v0→v2→v5=4+7=11。這里v0→v2我們用的是剛才計算出來的較小的4。此時我們也發(fā)現(xiàn)v0→v1→v2→v4=5要比v0→v1→v4=6還要小。所以v0到v4目前的最小距離是5，如下圖所示。
當我們要求v0到v3的最短距離時，通向v3的三條邊，除了v6沒有研究過外，v0→v1→v3的結果是8，而v0→v4→v3=5+2=7。因此，v0到v3的最短距離是7，如下圖所示。
它并不是一下子就求出了v0到v8的最短路徑，而是一步步求出它們之間頂點的最短路徑，過程中都是基于已經(jīng)求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得到你要的結果。
#define MAXVEX 9
#define INFINITY 65535
typedef int
/* 用于存儲最短路徑下標的數(shù)組 */
Patharc[MAXVEX];
typedef int
/* 用于存儲到各點最短路徑的權值和 */
ShortPathTable[MAXVEX];
/* Dijkstra算法，求有向網(wǎng)G的v0頂點到其余頂點v最短路徑P[v]及帶權長度D[v] */
/* P[v]的值為前驅頂點下標，D[v]表示v0到v的最短路徑長度和。 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v, w, k, min;
/* final[w]=1表示求得頂點v0至vw的最短路徑 */
int final[MAXVEX];
/* 初始化數(shù)據(jù) */
for (v = 0; v < G.numVertexes; v++)
{
/* 全部頂點初始化為未知最短路徑狀態(tài) */
final[v] = 0;
/* 將與v0點有連線的頂點加上權值 */
(*D)[v] = G.arc[v0][v];
/* 初始化路徑數(shù)組P為-1 */
(*P)[v] = -1;
}
/* v0至v0路徑為0 */
(*D)[v0] = 0;
/* v0至v0不需要求路徑 */
final[v0] = 1;
/* 開始主循環(huán)，每次求得v0到某個v頂點的最短路徑 */
for (v = 1; v < G.numVertexes; v++)
{
/* 當前所知離v0頂點的最近距離 */
min=INFINITY;
/* 尋找離v0最近的頂點 */
for (w = 0; w < G.numVertexes; w++)
{
if (!final[w] && (*D)[w] < min)
{
k=w;
/* w頂點離v0頂點更近 */
min = (*D)[w];
}
}
/* 將目前找到的最近的頂點置為1 */
final[k] = 1;
/* 修正當前最短路徑及距離 */
for (w = 0; w < G.numVertexes; w++)
{
/* 如果經(jīng)過v頂點的路徑比現(xiàn)在這條路徑的長度短的話 */
if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
{
/* 說明找到了更短的路徑，修改D[w]和P[w] */
/* 修改當前路徑長度 */
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
調用此函數(shù)前，其實我們需要為下圖的左圖準備鄰接矩陣MGraph的G，如下圖的右圖，并且定義參數(shù)v0為0。
1．程序開始運行，第4行final數(shù)組是為了v0到某頂點是否已經(jīng)求得最短路徑的標記，如果v0到vw已經(jīng)有結果，則final[w]=1。
2．第5～10行，是在對數(shù)據(jù)進行初始化的工作。此時final數(shù)組值均為0，表示所有的點都未求得最短路徑。D數(shù)組為{65535,1,5,65535,65535,65535,65535,65535,65535}。因為v0與v1和v2的邊權值為1和5。P數(shù)組全為0，表示目前沒有路徑。
3．第11行，表示v0到v0自身，權值和結果為0。D數(shù)組為{0,1,5,65535,65535,65535,65535,65535,65535}。第12行，表示v0點算是已經(jīng)求得最短路徑，因此final[0]=1。此時final數(shù)組為{1,0,0,0,0,0,0,0,0}。此時整個初始化工作完成。
4．第13～33行，為主循環(huán)，每次循環(huán)求得v0與一個頂點的最短路徑。因此v從1而不是0開始。
5．第15～23行，先令min為65535的極大值，通過w循環(huán)，與D[w]比較找到最小值min=1，k=1。
6．第24行，由k=1，表示與v0最近的頂點是v1，并且由D[1]=1，知道此時v0到v1的最短距離是1。因此將v1對應的final[1]設置為1。此時final數(shù)組為{1,1,0,0,0,0,0,0,0}。
7．第25～32行是一循環(huán)，此循環(huán)甚為關鍵。它的目的是在剛才已經(jīng)找到v0與v1的最短路徑的基礎上，對v1與其他頂點的邊進行計算，得到v0與它們的當前最短距離，如下圖所示。因為min=1，所以本來D[2]=5，現(xiàn)在v0→v1→v2=D[2]=min+3=4，v0→v1→v3=D[3]=min+7=8，v0→v1→v4=D[4]=min+5=6，因此，D數(shù)組當前值為{0,1,4,8,6,65535,65535,65535,65535}。而P[2]=1，P[3]=1，P[4]=1，它表示的意思是v0到v2、v3、v4點的最短路徑它們的前驅均是v1。此時P數(shù)組值為：{0,0,1,1,1,0,0,0,0}。
8．重新開始循環(huán)，此時v=2。第15～23行，對w循環(huán)，注意因為final[0]=1和fi-nal[1]=1，由第18行的!final[w]可知，v0與v1并不參與最小值的獲取。通過循環(huán)比較，找到最小值min=4，k=2。
9．第24行，由k=2，表示已經(jīng)求出v0到v2的最短路徑，并且由D[2]=4，知道最短距離是4。因此將v2對應的final[2]設置為1，此時final數(shù)組為：{1,1,1,0,0,0,0,0,0}。10．第25～32行。在剛才已經(jīng)找到v0與v2的最短路徑的基礎上，對v2與其他頂點的邊，進行計算，得到v0與它們的當前最短距離，如下圖所示，因為min=4，所以本來D[4]=6，現(xiàn)在v0→v2→v4=D[4]=min+1=5，v0→v2→v5=D[5]=min+7=11，因此，D數(shù)組當前值為：{0,1,4,8,5,11,65535,65535,65535}。而原本P[4]=1，此時P[4]=2，P[5]=2，它表示v0到v4、v5點的最短路徑它們的前驅均是v2。此時P數(shù)組值為：{0,0,1,1,2,2,0,0,0}。
11．重新開始循環(huán)，此時v=3。第15～23行，通過對w循環(huán)比較找到最小值min=5，k=4。
12．第24行，由k=4，表示已經(jīng)求出v0到v4的最短路徑，并且由D[4]=5，知道最短距離是5。因此將v4對應的final[4]設置為1。此時final數(shù)組為：{1,1,1,0,1,0,0,0,0}。
13．第25～32行。對v4與其他頂點的邊進行計算，得到v0與它們的當前最短距離，如下圖所示。因為min=5，所以本來D[3]=8，現(xiàn)在v0→v4→v3=D[3]=min+2=7，本來D[5]=11，現(xiàn)在v0→v4→v5=D[5]=min+3=8，另外v0→v4→v6=D[6]=min+6=11，v0→v4→v7=D[7]=min+9=14，因此，D數(shù)組當前值為：{0,1,4,7,5,8,11,14,65535}。而原本P[3]=1，此時P[3]=4，原本P[5]=2，此時P[5]=4，另外P[6]=4，P[7]=4，它表示v0到v3、v5、v6、v7點的最短路徑它們的前驅均是v4。此時P數(shù)組值為：{0,0,1,4,2,4,4,4,0}。
14．之后的循環(huán)就完全類似了。得到最終的結果，如下圖所示。此時final數(shù)組為：{1,1,1,1,1,1,1,1,1}，它表示所有的頂點均完成了最短路徑的查找工作。此時D數(shù)組為：{0,1,4,7,5,8,10,12,16}，它表示v0到各個頂點的最短路徑數(shù)，比如D[8]=1+3+1+2+3+2+4=16。此時的P數(shù)組為：{0,0,1,4,2,4,3,6,7}，這“串數(shù)字可能略為難理解一些。比如P[8]=7，它的意思是v0到v8的最短路徑，頂點v8的前驅頂點是v7，再由P[7]=6表示v7的前驅是v6，P[6]=3，表示v6的前驅是v3。這樣就可以得到，v0到v8的最短路徑為v8←v7←v6←v3←v4←v2←v1←v0，即v0→v1→v2→v4→v3→v6→v7→v8。
其實最終返回的數(shù)組D和數(shù)組P，是可以得到v0到任意一個頂點的最短路徑和路徑長度的。例如v0到v8的最短路徑并沒有經(jīng)過v5，但我們已經(jīng)知道v0到v5的最短路徑了。由D[5]=8可知它的路徑長度為8，由P[5]=4可知v5的前驅頂點是v4，所以v0到v5的最短路徑是v0→v1→v2→v4→v5。
也就是說，我們通過迪杰斯特拉（Dijkstra）算法解決了從某個源點到其余各頂點的最短路徑問題。從循環(huán)嵌套可以很容易得到此算法的時間復雜度為O(n2)，盡管有同學覺得，可不可以只找到從源點到某一個特定終點的最短路徑，其實這個問題和求源點到其他所有頂點的最短路徑一樣復雜，時間復雜度依然是O(n2)。
這就好比，你吃了七個包子終于算是吃飽了，就感覺很不劃算，前六個包子白吃了，應該直接吃第七個包子，于是你就去尋找可以吃一個就能飽肚子的包子，能夠滿足你的要求最終結果只能有一個，那就是用七個包子的面粉和餡做的一個大包子。這種只關注結果而忽略過程的思想是非常不可取的。
可如果我們還需要知道如v3到v5、v1到v7這樣的任一頂點到其余所有頂點的最短路徑怎么辦呢？此時簡單的辦法就是對每個頂點當作源點運行一次迪杰斯特拉（Dijkstra）算法，等于在原有算法的基礎上，再來一次循環(huán)，此時整個算法的時間復雜度就成了O(n3)。
弗洛伊德（Floyd）算法
下圖的左圖是一個最簡單的3個頂點連通網(wǎng)圖。
我們先定義兩個二維數(shù)組D[3][3]和P[3][3]，D代表頂點到頂點的最短路徑權值和的矩陣。P代表對應頂點的最小路徑的前驅矩陣，用來存儲路徑。在未分析任何頂點之前，我們將D命名為D-1，其實它就是初始的圖的鄰接矩陣。將P命名為P-1，初始化為圖中所示的矩陣。
因為只有三個頂點，因此需要查看v1→v0→v2，得到D-1[1][0]+D-1[0][2]=2+1=3。D-1[1][2]表示的是v1→v2的權值為5，我們發(fā)現(xiàn)D-1[1][2]>D-1[1][0]+D-1[0][2]，通俗的話講就是v1→v0→v2比直接v1→v2距離還要近。所以我們就讓D-1[1][2]=D-1[1][0]+D-1[0][2]=3，同樣的D-1[2][1]=3，于是就有了D0的矩陣。因為有變化，所以P矩陣對應的P-1[1][2]和P-1[2][1]也修改為當前中轉的頂點v0的下標0，于是就有了P0。也就是說D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}
接下來，其實也就是在D0和P0的基礎上繼續(xù)處理所有頂點經(jīng)過v1和v2后到達另一頂點的最短路徑，得到D1和P1、D2和P2完成所有頂點到所有頂點的最短路徑計算工作。
首先我們針對下圖的左網(wǎng)圖準備兩個矩陣D-1和P-1，D-1就是網(wǎng)圖的鄰接矩陣，P-1初設為P[i][j]=j這樣的矩陣，它主要用來存儲路徑。
代碼如下，注意因為是求所有頂點到所有頂點的最短路徑，因此Pathmatirx和ShortPathTable都是二維數(shù)組。
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* Floyd算法，求網(wǎng)圖G中各頂點v到其余頂點w最短
路徑P[v][w]及帶權長度D[v][w] */
void ShortestPath_Floyd(MGraph G, Pathmatirx *P,
ShortPathTable *D)
{
int v, w, k;
/* 初始化D與P */
for (v = 0; v < G.numVertexes; ++v)
for (w = 0; w < G.numVertexes; ++w)
{
/* D[v][w]值即為對應點間的權值 */
(*D)[v][w] = G.matirx[v][w];
/* 初始化P */
(*P)[v][w] = w;
}
}
for (k = 0; k < G.numVertexes; ++k)
{
for (v = 0; v < G.numVertexes; ++v)
{
for (w = 0; w < G.numVertexes; ++w)
{
if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
{
/* 如果經(jīng)過下標為k頂點路徑比原兩點間路徑更短 */
/* 將當前兩點間權值設為更小的一個 */
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
/* 路徑設置經(jīng)過下標為k的頂點 */
(*P)[v][w] = (*P)[v][k];
}
}
}
}
}
1．程序開始運行，第4～11行就是初始化了D和P，使得它們成為上圖的兩個矩陣。從矩陣也得到，v0→v1路徑權值是1，v0→v2路徑權值是5，v0→v3無邊連線，所以路徑權值為極大值65535。
2．第12～25行，是算法的主循環(huán)，一共三層嵌套，k代表的就是中轉頂點的下標。v代表起始頂點，w代表結束頂點。
3．當K=0時，也就是所有的頂點都經(jīng)過v0中轉，計算是否有最短路徑的變化。可惜結果是，沒有任何變化，如下圖所示。
4．當K=1時，也就是所有的頂點都經(jīng)過v1中轉。此時，當v=0時，原本D[0][2]=5，現(xiàn)在由于D[0][1]+D[1][2]=4。因此由代碼的第20行，二者取其最小值，得到D[0][2]=4，同理可得D[0][3]=8、D[0][4]=6，當v=2、3、4時，也修改了一些數(shù)據(jù)，請參考如x下圖5左圖中虛線框數(shù)據(jù)。由于這些最小權值的修正，所以在路徑矩陣P上，也要作處理，將它們都改為當前的P[v][k]值，見代碼第21行。
5．接下來就是k=2一直到8結束，表示針對每個頂點做中轉得到的計算結果，當然，我們也要清楚，D0是以D-1為基礎，D1是以D0為基礎，……，D8是以D7為基礎，就像我們曾經(jīng)說過的七個包子的故事，它們是有聯(lián)系的，路徑矩陣P也是如此。最終當k=8時，兩矩陣數(shù)據(jù)如下圖所示。
至此，我們的最短路徑就算是完成了，你可以看到矩陣第v0行的數(shù)值與迪杰斯特拉（Dijkstra）算法求得的D數(shù)組的數(shù)值是完全相同，都是{0,1,4,7,5,8,10,12,16}。而且這里是所有頂點到所有頂點的最短路徑權值和都可以計算出。
那么如何由P這個路徑數(shù)組得出具體的最短路徑呢？以v0到v8為例，從上圖的右圖第v8列，P[0][8]=1，得到要經(jīng)過頂點v1，然后將1取代0得到P[1][8]=2，說明要經(jīng)過v2，然后將2取代1得到P[2][8]=4，說明要經(jīng)過v4，然后將4取代2得到P[4][8]=3，說明要經(jīng)過v3，……，這樣很容易就推導出最終的最短路徑值為v0→v1→v2→v4→v3→v6→v7→v8。
求最短路徑的顯示代碼可以這樣寫。
for (v = 0; v < G.numVertexes; ++v)
{
for (w = v + 1; w < G.numVertexes; w++)
{
printf("v%d-v%d weight: %d ", v, w, D[v][w]);
/* 獲得第一個路徑頂點下標 */
k = P[v][w];
/* 打印源點 */
printf(" path: %d", v);
/* 如果路徑頂點下標不是終點 */
while (k != w)
{
/* 打印路徑頂點 */
printf(" -> %d", k);
/* 獲得下一個路徑頂點下標 */
k = P[k][w];
}
/* 打印終點 */
printf(" -> %d\n", w);
}
printf("\n");
}
