杜衡吉

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）28-0079-02

1 概述

最短路徑問題是指在一個(gè)非負(fù)權(quán)值圖中找出兩個(gè)指定節(jié)點(diǎn)間的一條權(quán)值之和最小的路徑。Dijkstra 算法在很多計(jì)算機(jī)專業(yè)可均有介紹，如數(shù)據(jù)結(jié)構(gòu)，離散數(shù)學(xué)等，但大都比較粗略。迪克斯特拉算法是經(jīng)典的求解最短路徑問題的方法，是按路徑長(zhǎ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中找到起源點(diǎn) V0 到圖中其余各點(diǎn)的最短路徑。

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中頂點(diǎn)集合V分成兩個(gè)子集，第一個(gè)子集是已求出最短路徑的頂點(diǎn)集合，用V1表示，初始化時(shí)V1中只有一個(gè)起源點(diǎn)，以后每求得一條最短路徑 ， 就將被選定點(diǎn)加入到集合V1中，直到圖中全部頂點(diǎn)都依次添加到到V1中，算法就結(jié)束了；第二個(gè)集合為G中其余未確定最短路徑的頂點(diǎn)集合，用V2表示，按最短路徑長(zhǎng)度的遞增次序依次把第二個(gè)集合V2中的被選頂點(diǎn)加入集合V1中。特別，在加入的過程中，總保持從起源點(diǎn)v0到V1中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v0到V2中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，V1中的頂點(diǎn)的距離就是從v0到此頂點(diǎn)的最短路徑長(zhǎng)度，V2中的頂點(diǎn)的距離，是從v0到此頂點(diǎn)只包括V1中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。

2）算法具體步驟：

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

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

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

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

4 算法實(shí)例

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

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

5 算法代碼實(shí)現(xiàn)

測(cè)試案例如圖2所示：

#include

#include

#define M 100

#define N 100

using namespace std；

typedef struct node

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

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

int e； //邊數(shù)

}MGraph；

void Dpath（MGraph g，int *dist，int *path，int v0） //v0表示源點(diǎn)

{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的前一個(gè)頂點(diǎn)

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） //打印最短路徑上的各個(gè)頂點(diǎn)

{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； //表示輸入的頂點(diǎn)數(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； //輸入源頂點(diǎn)

Dpath（g，dist，path，v0）；

for（i=0；i

{if（i！=v0）

{ Apath（path，i，v0）；

cout<

return 0； }

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

6 小結(jié)

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

參考文獻(xiàn)：

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

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

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