Dijkstra算法設計與實現

杜衡吉

摘要：最短路徑算法在各領域應用廣泛，大多《離散數學》的圖論部分最短路徑算法講解較為粗略，不便于學生學習和實踐。經過多年教學總結，對最短路徑算法給出設計和實現，有利于學生對本知識的掌握和實踐應用。

關鍵詞：最短路徑；離散數學； Dijkstra算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）28-0079-02

1 概述

最短路徑問題是指在一個非負權值圖中找出兩個指定節點間的一條權值之和最小的路徑。Dijkstra 算法在很多計算機專業可均有介紹，如數據結構，離散數學等，但大都比較粗略。迪克斯特拉算法是經典的求解最短路徑問題的方法，是按路徑長度遞增的次序來產生最短路徑的算法[1]。

最短路徑問題描述：設n，m帶權圖 G=，V={v0，v1，…，vn-1}，E={e1，e2，…，em}，其中假設每條邊ei 的權值為 wi，單源的最短路徑就是從圖G中找到起源點 V0 到圖中其余各點的最短路徑。

2 最短路徑概念

帶權圖G=， 其中W：ER， eE，w（e）稱作e的權。 若vi和vj相鄰e=（vi，vj）， 記w（vi，vj）=w（vi，vj） ， 若vi，vj不相鄰， 記w（vi，vj）=。通路L的權是指L的所有邊的權值之和， 記作w（L），u和v之間的最短路徑指的是 u和v之間邊權最小的通路[2]。

3 Dijkstra算法描述

1）算法基本過程：設帶權圖G=，把圖G中頂點集合V分成兩個子集，第一個子集是已求出最短路徑的頂點集合，用V1表示，初始化時V1中只有一個起源點，以后每求得一條最短路徑 ， 就將被選定點加入到集合V1中，直到圖中全部頂點都依次添加到到V1中，算法就結束了；第二個集合為G中其余未確定最短路徑的頂點集合，用V2表示，按最短路徑長度的遞增次序依次把第二個集合V2中的被選頂點加入集合V1中。特別，在加入的過程中，總保持從起源點v0到V1中各頂點的最短路徑長度不大于從源點v0到V2中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，V1中的頂點的距離就是從v0到此頂點的最短路徑長度，V2中的頂點的距離，是從v0到此頂點只包括V1中的頂點為中間頂點的當前最短路徑長度。

2）算法具體步驟：

a.初始時，V1只包含源點，即V1={ v0}，v0的距離為0。V2包含除v0外的其他頂點，即： V2={ v1， v2…，vn-1}。定義集合V2中的頂點的距離：若v0與V2中頂點v有邊，則dist（v）=w（v0，v）正常有權值，若v0與v點不相鄰，則dist（v）= ∞。

b.從V2中選取一個點k加入V1中，選擇公式dist（k）=min（dist（v） | v∈U），把k加入V1中（該選定的距離就是v0到k的最短路徑長度）。此時V1= V1∪{k}，同時V2集合中刪除k點，即V2= V2-{k}。

c.以k為新考慮的中間點，修改V2中各頂點的距離；若從源點v0到頂點v的距離（經過頂點k）比原來距離短，則修改頂點 v的距離值，否則v的距離值不變，修改公式dist（v）=min{dist（v），dist（k）+dist（k，v）}[3]。

d.重復步驟b和c直到V1=V，算法停止。

4 算法實例

1）先給出一個無向圖G=，如圖1所示：

用Dijkstra算法找出以A為起點的單源最短路徑步驟如表1：

5 算法代碼實現

測試案例如圖2所示：

#include

#include

#define M 100

#define N 100

using namespace std；

typedef struct node

{int m[N][M]； //鄰接矩陣

int n； //頂點數

int e； //邊數

}MGraph；

void Dpath（MGraph g，int *dist，int *path，int v0） //v0表示源點

{int i，j，k；

bool *ved=（bool *）malloc（sizeof（bool）*g.n）；

for（i=0；i

{if（g.m[v0][i]>0&&i！=v0）

{dist[i]=g.m[v0][i]；

path[i]=v0； } //path記錄最短路徑上從v0到i的前一個頂點

else

{dist[i]=INT_MAX； //若i不與v0直接相鄰，則權值置為無窮大

path[i]=-1； }

ved[i]=false；

path[v0]=v0；

dist[v0]=0； }

ved[v0]=true；

for（i=1；i

{int min=INT_MAX；

int u；

for（j=0；j

{if（ved[j]==false&&dist[j]

{ min=dist[j]；

u=j；} }

ved[u]=true；

for（k=0；k

{ if（ved[k]==false&&g.m[u][k]>0&&min+g.m[u][k]

{dist[k]=min+g.m[u][k]；

path[k]=u； }}}}

void Apath（int *path，int v，int v0） //打印最短路徑上的各個頂點

{stack s；

int u=v；

while（v！=v0）

{ s.push（v）；

v=path[v]； }

s.push（v）；

while（！s.empty（））

{cout<

s.pop（）；}}

int main（int argc， char *argv[]）

{ int n，e； //表示輸入的頂點數和邊數

while（cin>>n>>e&&e！=0）

{int i，j；

int s，t，w； //表示存在一條邊s->t，權值為w

MGraph g；

int v0；

int *dist=（int *）malloc（sizeof（int）*n）；

int *path=（int *）malloc（sizeof（int）*n）；

for（i=0；i

for（j=0；j

g.m[i][j]=0；

g.n=n；

g.e=e；

for（i=0；i

{cin>>s>>t>>w；

g.m[s][t]=w； }

cin>>v0； //輸入源頂點

Dpath（g，dist，path，v0）；

for（i=0；i

{if（i！=v0）

{ Apath（path，i，v0）；

cout<

return 0； }

測試結果如圖3所示：

6 小結

作為一門計算機的專業基礎課《離散數學》在計算機學科領域中發揮了重要的作用。最短路徑算法在很多方面有著重要的應用，針對教材中Dijkstra最短路徑算法講解粗略，學生學習困難等問題，本人結合多年的教學經驗，對Dijkstra算法求最短路徑給出了詳細的算法設計和實現，對這部分內容的教學幫助明顯。

參考文獻：

[1] 李妍妍.Dijkstra最短路徑分析算法的優化實現[J].測繪與空間地理信息，2014，37（5）：172-190.

[2] 耿素云，屈婉玲，張立昂.離散數學[M]. 5版.北京：清華大學出版社，2013：128-130.

[3] 曹曉東，原旭.離散數學及算法 [M].北京：機械工業出版社，2012：240-244.