Dijkstra算法模型設(shè)計(jì)與實(shí)現(xiàn).doc

《Dijkstra算法模型設(shè)計(jì)與實(shí)現(xiàn).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、Dijkstra算法模型設(shè)計(jì)與實(shí)現(xiàn)一、Dijkstra算法概述Dijkstra算法是一種點(diǎn)對(duì)多點(diǎn)的集中式最短路徑算法，即尋找網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑。Dijkstra算法通過(guò)對(duì)路徑的長(zhǎng)度進(jìn)行迭代，從而計(jì)算出到達(dá)目的節(jié)點(diǎn)的最短路徑。其基本思想是按照路徑長(zhǎng)度增加的順序來(lái)尋找最短路徑，顯然有：到達(dá)目的節(jié)點(diǎn)的最短路徑中最短的肯定是節(jié)點(diǎn)的最近節(jié)點(diǎn)所對(duì)應(yīng)的單條鏈路，最短路徑中下一個(gè)最短的肯定是節(jié)點(diǎn)的下一個(gè)最近的鄰節(jié)點(diǎn)所對(duì)應(yīng)的單條鏈路，或者是通過(guò)前面選定的節(jié)點(diǎn)的最短的由兩條鏈路組成的的路徑，依次類推。二、Dijk

2、stra算法描述設(shè)每個(gè)節(jié)點(diǎn)標(biāo)定的到達(dá)目的節(jié)點(diǎn)1的最短路徑長(zhǎng)度估計(jì)為，如果在迭代的過(guò)程中，已變成一個(gè)確定的值，稱節(jié)點(diǎn)為永久標(biāo)定的節(jié)點(diǎn)，這些永久標(biāo)定的節(jié)點(diǎn)的集合用表示。在算法的每一步中，在以外的節(jié)點(diǎn)中，必定是選擇與目的節(jié)點(diǎn)1最近的節(jié)點(diǎn)加入到集合中。具體算法如下：1.初始化，即，，，。（若，則）。2.尋找下一個(gè)與目的節(jié)點(diǎn)最近的節(jié)點(diǎn)，即求使下式成立的。置。如果包括了所有的節(jié)點(diǎn)，則算法結(jié)束。，3.更改標(biāo)定值，即對(duì)所有的，置，返回第2步。三、Dijkstra算法實(shí)現(xiàn)根據(jù)Dijkstra算法描述編寫(xiě)程序進(jìn)行實(shí)現(xiàn)，程序中采用鄰接

3、矩陣表示一個(gè)有向圖，輸入為該圖的鄰接矩陣以及目的節(jié)點(diǎn)，輸出為圖中各點(diǎn)的鄰接關(guān)系，依照次鄰接關(guān)系可得到到達(dá)目的節(jié)點(diǎn)的最短路徑。程序用C語(yǔ)言編寫(xiě)，GCC環(huán)境編譯，具體代碼見(jiàn)附錄。四、運(yùn)行結(jié)果及分析選擇一具有7個(gè)節(jié)點(diǎn)的有向圖進(jìn)行實(shí)驗(yàn)，其各邊權(quán)重及拓?fù)浣Y(jié)構(gòu)如下所示：圖1實(shí)驗(yàn)用圖選取節(jié)點(diǎn)1為目的節(jié)點(diǎn)，運(yùn)行程序：1.輸入表示該圖的鄰接矩陣，不相鄰的節(jié)點(diǎn)間鏈路權(quán)值用-1表示，代表無(wú)窮大；2.輸入目的節(jié)點(diǎn)編號(hào)；3.得到輸出結(jié)果，如下圖所示。輸出結(jié)果圖2程序運(yùn)行截圖1將輸出結(jié)果用圖表示為：圖3到達(dá)目的節(jié)點(diǎn)1的最短路由更改目的節(jié)點(diǎn)，

4、選取目的節(jié)點(diǎn)為節(jié)點(diǎn)5，重新運(yùn)行程序，得到結(jié)果如下：目的節(jié)點(diǎn)更改為5圖4程序運(yùn)行截圖2輸出結(jié)果用圖表示為：圖5到達(dá)目的節(jié)點(diǎn)5的最短路由選擇不同的目的節(jié)點(diǎn)，利用此程序均能得出正確的最短路徑，證明了程序的正確性。達(dá)到了較好的效果。附源代碼：#include#include#defineN7/*節(jié)點(diǎn)個(gè)數(shù)*/intmain(){doublee[N][N],d[N];intv;/*目的節(jié)點(diǎn)*/inti,j,min,x;longp=0;intpath[N];/*節(jié)點(diǎn)從0開(kāi)始計(jì)數(shù)*/for(

5、i=0;i

6、=1<

7、ile(1){min=32767;for(j=0;jd[j]){i=j;min=d[j];}}p

8、=1<=(1<d[i]+e[j][i]){min=d[i]+e[j][i];x=i;}if(d[j]>min){d[j]=min;path[j]=x;}}}print

9、f("***result:***");for(i=0;iP%d",i+1,path[i]+1);}exit(EXIT_SUCCESS);}