Dijkstra算法設(shè)計與實現(xiàn)

杜衡吉

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

關(guān)鍵詞：最短路徑；離散數(shù)學； Dijkstra算法

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

1 概述

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

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

2 最短路徑概念

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

3 Dijkstra算法描述

1）算法基本過程：設(shè)帶權(quán)圖G=，把圖G中頂點集合V分成兩個子集，第一個子集是已求出最短路徑的頂點集合，用V1表示，初始化時V1中只有一個起源點，以后每求得一條最短路徑 ， 就將被選定點加入到集合V1中，直到圖中全部頂點都依次添加到到V1中，算法就結(jié)束了；第二個集合為G中其余未確定最短路徑的頂點集合，用V2表示，按最短路徑長度的遞增次序依次把第二個集合V2中的被選頂點加入集合V1中。特別，在加入的過程中，總保持從起源點v0到V1中各頂點的最短路徑長度不大于從源點v0到V2中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，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）正常有權(quán)值，若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的距離（經(jīng)過頂點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 算法代碼實現(xiàn)

測試案例如圖2所示：

#include

#include

#define M 100

#define N 100

using namespace std；

typedef struct node

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

int n； //頂點數(shù)

int e； //邊數(shù)

}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直接相鄰，則權(quán)值置為無窮大

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； //表示輸入的頂點數(shù)和邊數(shù)

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

{int i，j；

int s，t，w； //表示存在一條邊s->t，權(quán)值為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； }

測試結(jié)果如圖3所示：

6 小結(jié)

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

參考文獻：

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

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

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