基于Dijkstra的多源點最短路徑求解算法的設計與分析

祝國明

摘要：Dijkstra是圖的單源點最短路徑算法，本文介紹利用Dijkstra算法進行多源點最短路徑求解的方法，不僅能統(tǒng)計任意兩點間的最短路徑長度，而且能夠求解兩點間的具體路徑并以堆棧顯示，因此有助于算法的學習、比較及拓展，提高計算思維能力。

關鍵詞：Dijkstra算法;最短路徑;多源點

中圖分類號：G642? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）16-0177-02

開放科學（資源服務）標識碼（OSID）：

在帶權有向圖或是無向圖中，Dijkstra[1]算法是單源點算法，既然可以實現(xiàn)單源點到任意終點的最短路徑求解，那么就可求解并列出任意兩點間的最短路徑長度表。同時還可以表達任意兩點間的具體“路線”，從而得以求解多源點最短路徑的問題。

1 需要解決的問題

1）以二維表格形式顯示多源點下的最短路徑長度，即任意兩點間的最短路徑表。

2）以二維表格形式顯示多源點下的最短具體“路線”表，即任意兩點間的最短具體短路徑可以通過表格來查看。

3）以堆棧的方式，輸出具體兩點的最短路徑線。

2 問題思維

1）解決多源點最短路徑問題

因為能夠求解單源點V0到所有終點Vn的最短路徑，所以就可以用同樣的方式求解其他源點到所有終點的最短路徑問題，只須用循環(huán)輪換源點即可。

2）單源點最短路徑問題

這個問題可基于Dijkstra算法解決，假定原圖矩陣數(shù)據(jù)為G[N][N]則基本思想如下：

第一，從圖的矩陣數(shù)據(jù)中G[N][N]取出源點V0到各終點Vn “直達”路徑Dis[i]=G[0][i]。

第二，設定S[N]為源點V0到終點V1至Vn最短路徑是否確定的初態(tài)。

第三，采用循環(huán)機制，每次從Dis[N]中選取最小的路徑權值Dis[i]，此時源點V0到終點Vi 的最短路徑確定，修改S[i]標識，找出所有與Vi有關的出度點Vj，如果Dis[j]>Dis[i]+G[i][j]，則修正源點到終點j的最短路徑Dis[j]=dis[i]+G[i][j]。

至此，源點到各終點的最短路徑長度得以解決。

3）解決路徑記錄問題

要確切知道，從源點到一終點的具體路徑線，可以以記錄結點“前驅”的方式進行，模式Dis[j] =dis[i]+G[i][j]表示源點到各終點j的最短路徑在不斷地修改，因為點j是i的出度，最短路徑dis[i]是確定值，所以可以將點i記錄為點j的最短路徑“前驅”，pre [j]=i+1，從而通過終點可以找出具體路徑結果。

4）輸出路徑問題

由于在最短路徑中，各結點只是記錄了自身“前驅”結點，因此可以從終點沿路徑反向找出全部的路徑，而這種特點可以用堆棧結構完成。

3 設計實現(xiàn)

3.1 最短路徑長度及最短路徑結點“前驅”表

多源點下實現(xiàn)任意點到點最短路徑表及任意兩點間最短路徑中的結點“前驅”表，其對應算法實現(xiàn)如下：

void DjsM（int dis[][N]，int s[][N]，int pre[][N]，int G[][N]）

{ int i，j，k，min，u，v;

for（i=0;i

{ s[i][0]=i;//源點自身最短路徑是確定的

for （k=1;k

{ min=max;

for（j=0;j

if（s[i][j]==-1&&dis[i][j]

{ min=dis[i][j];

u=j;

}

s[i][u]=u;//最短路徑確定的頂點，加入s集合

for（v=0;v

if（v！=i&&G[u][v]

if（dis[i][v]>dis[i][u]+G[u][v]）//修正源點到v的最短路徑dis[v]

{dis[i][v]=dis[i][u]+G[u][v];

pre[i][v]=u+1;//記錄對應“前驅”

}

}

}

}

3.2 圖的任意兩點間的最短路徑堆棧式輸出

利用最短路徑“前驅表”，用堆棧的方式輸出源點到終點的路徑線。對應處理過程如下：

（1）用于存儲圖結點序號的堆棧，包括建棧、進棧、出棧基本操作。

struct node//棧模型及實體

{ int st[N];

int top;

int len;

}ss;

void push（int x）//每次進棧一個結點

{? if（ss.top==N-1）

printf（"棧已滿！"）;

else

{ ss.top++;

ss.st[ss.top]=x;//進棧一個結點

}

}

void pop（）

{ if（ss.top== -1）//空棧判定

{printf（"棧已空！"）;

return;

}

while（ss.top！=-1）//具體路線顯示

{if （ss.top）

printf（"V%d->"，ss.st[ss.top]）;

else

printf（"V%d"，ss.st[ss.top]）;

ss.top--;

}

}

（2）輸出源點到終點的具體路線。

ss.len=N;ss.top=-1;

printf（"路徑："）;

push（n）;//終點進棧

p=pre[m-1][n-1];//終點的前驅結點序號

while（p）//有前驅，繼續(xù)

{ push（p）;

p=pre[m-1][p-1];//續(xù)找“前驅”，p-1為p結點下標

}

push（m）;//源點進棧

pop（）;//清空棧，得到路線結果

printf（"＼n源點到終點的前驅路徑表，元素值為0表示此點無前驅，即“直達”現(xiàn)象＼n"）;

for（m=0;m

{for（n=0;n

printf（"%3d"，pre[m][n]）;

printf（"＼n"）;

}

4 算法測試分析

本算法的測試用例是一個有向或無向圖的矩陣數(shù)據(jù)，算法處理結果分兩類，一是圖的最短路徑長度二維表格，從表中可以直接查看任意兩點間的最短路徑長度;二是圖的最短路徑結點“前驅”二維表格，可以查看或是輸出任意兩點最短路徑下的“具體路線”。算法的結果運算正確，多源點最短路徑及對應路線求解正確。

5 結束語

本文介紹了基于Dijkstra算法的多源點最短路徑及對應路線的求解過程，其問題的求解方法及效果可以類比于Floyd[2]]弗若伊德多源點算法，有利于提高程序思維、計算思維能力，有助于相關算法的學習與借鑒。

參考文獻：

[1] 張小艷，李占利. 數(shù)據(jù)結構與算法設計（C語言版）[M]. 西安電子科技大學出版社，2015.

[2] 顧澤元，劉文強. 數(shù)據(jù)結構[M].北航出版社，2014.

【通聯(lián)編輯：王力】