迪杰斯特拉算法和floyd算法實現(xiàn)無向圖的最短路徑的計算和求解

《迪杰斯特拉算法和floyd算法實現(xiàn)無向圖的最短路徑的計算和求解》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、12沈陽理工大學算法與創(chuàng)新設計課程設計摘要本次課程設計主要核心為利用迪杰斯特拉算法和Floyd算法實現(xiàn)無向圖的最短路徑的計算和求解。要求理解算法的具體實現(xiàn)流程、學會正確使用該算法求解實際問題。本次課程設計具體內(nèi)容是：通過對兩個算法的理解與應用來比較兩個算法的優(yōu)缺點。本程序要求結合最短路算法以及相應的數(shù)據(jù)結構的定義和使用，實現(xiàn)一個最短路徑算法的簡單應用。本課程設計是對書本知識的簡單應用，以此培養(yǎng)大家用書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)以科學理論和工程上能力的技術，規(guī)范地開發(fā)大型、復雜、高質(zhì)量的應用軟件和系統(tǒng)軟件。

2、關鍵字：迪杰斯特拉算法，F(xiàn)loyd算法，最短路徑，算法設計，數(shù)據(jù)結構1212沈陽理工大學算法與創(chuàng)新設計課程設計目錄摘要1一、Dijkstra算法31.1定義概覽31.2算法描述31.2.1算法思想：31.1.2算法步驟41.3算法代碼實現(xiàn)51.4算法實例6二、Floyd算法82.1定義概覽82.2算法描述82.2.1算法思想原理82.3算法代碼實現(xiàn)11三、結論12四、參考文獻131212沈陽理工大學算法與創(chuàng)新設計課程設計一、Dijkstra算法1.1定義概覽Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他

3、所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結構，圖論，運籌學等等。注意該算法要求圖中不存在負權邊。問題描述：在無向圖G=(V,E)中，假設每條邊E[i]的長度為w[i]，找到由頂點V0到其余各點的最短路徑。?1.2算法描述1.2.1算法思想：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑,就將加入到集合S

4、中，直到全部頂點都加入到S中，算法就結束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。1.1.2算法步驟：a.初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其余頂點}，若v與U中頂點u有邊，

5、則正常有權值，若u不是v的出邊鄰接點，則權值為∞。1212沈陽理工大學算法與創(chuàng)新設計課程設計b.從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權。d.重復步驟b和c直到所有頂點都包含在S中。?執(zhí)行動畫過程如下圖1.3算法代碼實現(xiàn)：constintMAXINT=32767;constintMAXNUM=1

6、0;intdist[MAXNUM];intprev[MAXNUM]; intA[MAXUNM][MAXNUM]; voidDijkstra(intv0) { boolS[MAXNUM];//判斷是否已存入該點到S集合中 intn=MAXNUM; for(inti=1;i<=n;++i){ dist[i]=A[v0][i]; S[i]=false;//初始都未用過該點 if(dist[i]==MAXINT) prev[i]=-1; else 1212沈陽理工大學算法與創(chuàng)新設計課程設計prev[i]=v0; } dist[v0]=0; 　S[

7、v0]=true;　　 　for(inti=2;i<=n;i++) 　　{ intmindist=MAXINT; intu=v0;　　//找出當前未使用的點j的dist[j]最小值 for(intj=1;j<=n;++j) if((!S[j])&&dist[j]

8、[j])//在通過新加入的u點路徑找到離v0點更短的路徑　　{ dist[j]=dist[u]+A[u][j];//更新dist prev[j]=u;//記錄前驅(qū)頂點　　} 　　} 　　} }