杜衡吉
摘要:最短路徑算法在各領(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=
2 最短路徑概念
帶權(quán)圖G=
3 Dijkstra算法描述
1)算法基本過程:設(shè)帶權(quán)圖G=
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=
用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 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.