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

祝國明

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

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

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

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

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

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

1 需要解決的問題

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

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

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

2 問題思維

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

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

2）單源點最短路徑問題

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

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

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

第三，采用循環機制，每次從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 設計實現

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

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

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）//有前驅，繼續

{ push（p）;

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

}

push（m）;//源點進棧

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

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

for（m=0;m

{for（n=0;n

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

printf（"＼n"）;

}

4 算法測試分析

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

5 結束語

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

參考文獻：

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

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

【通聯編輯：王力】