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

《dijkstra算法設(shè)計與實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、Dijkstra算法設(shè)計與實現(xiàn)　　摘要：最短路徑算法在各領(lǐng)域應(yīng)用廣泛，大多《離散數(shù)學(xué)》的圖論部分最短路徑算法講解較為粗略，不便于學(xué)生學(xué)習(xí)和實踐。經(jīng)過多年教學(xué)總結(jié)，對最短路徑算法給出設(shè)計和實現(xiàn)，有利于學(xué)生對本知識的掌握和實踐應(yīng)用?！　￡P(guān)鍵詞：最短路徑；離散數(shù)學(xué)；Dijkstra算法　　中圖分類號：TP311文獻標(biāo)識碼：A文章編號：1009-3044（2016）28-0079-02　　1概述　　最短路徑問題是指在一個非負(fù)權(quán)值圖中找出兩個指定節(jié)點間的一條權(quán)值之和最小的路徑。Dijkstra算法在很多計算機專業(yè)可均有介紹，如數(shù)據(jù)結(jié)構(gòu)，離散數(shù)學(xué)等，但大都比較粗略。迪克斯特拉算法是經(jīng)典的

2、求解最短路徑問題的方法，是按路徑長度遞增的次序來產(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到圖中其余各點的最短路徑?！　?最短路徑概念　　帶權(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)值之和，7記作w（L），u和v之間的最短路徑指的是u和v之間邊權(quán)最小的通路[2]?！　?/p>

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

4、到此頂點的最短路徑長度，V2中的頂點的距離，是從v0到此頂點只包括V1中的頂點為中間頂點的當(dāng)前最短路徑長度?！　?）算法具體步驟：　　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）=∞?！　.從V2中選取一個點k加入V1中，選擇公式dist（k）=min（dist（v）

5、v∈U），把k加入V1中（該選定的距離就是v0到k的最短路徑長度）。此時V1=V1∪{k}，

6、同時V2集合中刪除k點，即V2=V2-{k}。7　　c.以k為新考慮的中間點，修改V2中各頂點的距離；若從源點v0到頂點v的距離（經(jīng)過頂點k）比原來距離短，則修改頂點v的距離值，否則v的距離值不變，修改公式dist（v）=min{dist（v），dist（k）+dist（k，v）}[3]?！　.重復(fù)步驟b和c直到V1=V，算法停止?！　?算法實例　　1）先給出一個無向圖G=，如圖1所示：　　用Dijkstra算法找出以A為起點的單源最短路徑步驟如表1：　　5算法代碼實現(xiàn)　　測試案例如圖2所示：　　#include　　#include　　#defineM100　　#defin

7、eN100　　usingnamespacestd；　　typedefstructnode　　{intm[N][M]；//鄰接矩陣　　intn；//頂點數(shù)　　inte；//邊數(shù)　　}MGraph；　　voidDpath（MGraphg，int*dist，int*path，intv0）//v0表示源點　　{inti，j，k；7　　bool*ved=（bool*）malloc（sizeof（bool）*g.n）；　　for（i=0；i0&&i！=v0）　　{dist[i]=g.m[v0][i]；　　path[i]=v0；

8、}//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