祝國明

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

關(guān)鍵詞：Dijkstra算法;最短路徑;多源點(diǎn)

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

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

1 需要解決的問題

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

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

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

2 問題思維

1）解決多源點(diǎn)最短路徑問題

因?yàn)槟軌蚯蠼鈫卧袋c(diǎn)V0到所有終點(diǎn)Vn的最短路徑，所以就可以用同樣的方式求解其他源點(diǎn)到所有終點(diǎn)的最短路徑問題，只須用循環(huán)輪換源點(diǎn)即可。

2）單源點(diǎn)最短路徑問題

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

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

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

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

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

3）解決路徑記錄問題

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

4）輸出路徑問題

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

3 設(shè)計(jì)實(shí)現(xiàn)

3.1 最短路徑長度及最短路徑結(jié)點(diǎn)“前驅(qū)”表

多源點(diǎn)下實(shí)現(xiàn)任意點(diǎn)到點(diǎn)最短路徑表及任意兩點(diǎn)間最短路徑中的結(jié)點(diǎn)“前驅(qū)”表，其對應(yīng)算法實(shí)現(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;//源點(diǎn)自身最短路徑是確定的

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;//最短路徑確定的頂點(diǎn)，加入s集合

for（v=0;v

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

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

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

pre[i][v]=u+1;//記錄對應(yīng)“前驅(qū)”

}

}

}

}

3.2 圖的任意兩點(diǎn)間的最短路徑堆棧式輸出

利用最短路徑“前驅(qū)表”，用堆棧的方式輸出源點(diǎn)到終點(diǎn)的路徑線。對應(yīng)處理過程如下：

（1）用于存儲圖結(jié)點(diǎn)序號的堆棧，包括建棧、進(jìn)棧、出?；静僮鳌?/p>

struct node//棧模型及實(shí)體

{ int st[N];

int top;

int len;

}ss;

void push（int x）//每次進(jìn)棧一個(gè)結(jié)點(diǎn)

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

printf（"棧已滿！"）;

else

{ ss.top++;

ss.st[ss.top]=x;//進(jìn)棧一個(gè)結(jié)點(diǎn)

}

}

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）輸出源點(diǎn)到終點(diǎn)的具體路線。

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

printf（"路徑："）;

push（n）;//終點(diǎn)進(jìn)棧

p=pre[m-1][n-1];//終點(diǎn)的前驅(qū)結(jié)點(diǎn)序號

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

{ push（p）;

p=pre[m-1][p-1];//續(xù)找“前驅(qū)”，p-1為p結(jié)點(diǎn)下標(biāo)

}

push（m）;//源點(diǎn)進(jìn)棧

pop（）;//清空棧，得到路線結(jié)果

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

for（m=0;m

{for（n=0;n

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

printf（"＼n"）;

}

4 算法測試分析

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

[2] 顧澤元，劉文強(qiáng). 數(shù)據(jù)結(jié)構(gòu)[M].北航出版社，2014.

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