最短路徑算法的研究畢業(yè)設(shè)計

上傳人：奔*** IP屬地：河北更新時間：2024-03-02 格式：doc 頁數(shù)：45 大?。?17.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩44頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　本科畢業(yè)設(shè)計(論文)　　題目名稱：最短路徑算法的研究 　　學(xué) 院：計算機(jī)科學(xué)技術(shù) 　　專業(yè)年級：　　計算機(jī)科學(xué)與技術(shù)（師范）08級 　　學(xué)生姓名：

2、 　　指導(dǎo)教師： xx 　　　二○一二年六月八日　　摘要　　本文目的在于研究關(guān)于最短路徑的算法，為研究最短路徑問題

3、在一些出行問題、管理問題、工程問題及實際生活問題中的應(yīng)用，為企業(yè)和個人提供方便的選擇方法。同時，也為其他的同學(xué)提供一些解題的思路與方法，為他們提供有利的資源。最后應(yīng)用蟻群算法來解決浙江旅行商問題。　　通過應(yīng)用最短路徑算法中的蟻群算法來解決浙江旅行商問題，以各城市經(jīng)緯度作為初始條件，通過MATLAB程序計算最短路徑，并畫出最短路線圖。　　關(guān)鍵詞：最短路徑算

4、法；最短路徑應(yīng)用；蟻群算法；浙江旅行商　　Abstract　　In this paper, the purpose is to collect the shortest path algorithm about common for the shortest path problem in some travel p

5、roblems, management, engineering problems and practical application of life, for enterprise and individual with convenient selection method. At the same time, the students for the mathematical modeling provide some ideas

6、 and methods for problem solving, provide favorable resources for the game. At last, by use of ant colony algorithm to solve the zhejiang traveling sale　　Key words：The shortest path algorithm, The sh

7、ortest path application, ant colony algorithm, Zhejiang traveling salesma　　目錄　　摘要I　　AbstractII<p&

8、gt;　　第1章緒論1　　1.1 選題的意義及目的1　　1.1.1 選題的意義1　　1.1.2 選題的目的1　　1.2 選題經(jīng)過及國內(nèi)外動態(tài)1　　1.2.1 選題經(jīng)過1&

9、lt;/p>　　1.2.2 選題的國內(nèi)外動態(tài)2　　第2章最短路徑算法的介紹3　　2.1Dijkstra 算法3　　2.1.1 算法介紹及適用條件和范圍3　　2.1.2 算法描述和算法實現(xiàn)3<p&

10、gt;　　2.1.3 具體算法分析4　　2.2 A* 算法8　　2.2.1 算法介紹及適用條件和范圍8　　2.2.2 算法描述和算法實現(xiàn)9　　2.2.3 具體算法分析9　　2.3 Bellman-Ford 算

11、法11　　2.3.1 算法介紹及適用條件和范圍11　　2.3.2 算法描述和算法實現(xiàn)11　　2.3.3 具體算法設(shè)計12　　2.4 Topological Sort 算法15　　2.4.1 算法介紹及適用條件和

12、范圍15　　2.4.2 算法描述和算法實現(xiàn)16　　2.4.3 具體算法設(shè)計16　　2.5 SSSP On DAG 算法20　　2.5.1 算法介紹及適用條件和范圍20　　2.5.2 算法描述和算法實現(xiàn)21&l

13、t;/p>　　2.6 Floyd 算法21　　2.6.1 算法介紹及適用條件和范圍21　　2.6.2 算法描述和算法實現(xiàn)21　　2.6.3 算法具體分析22　　第3章最短路徑算法的比較26<p

14、>　　第4章最短路徑算法的應(yīng)用28　　4.1 TSP問題的介紹28　　4.2 TSP問題算法的介紹28　　4.2.1 貪心算法28　　4.2.2 模擬退火算法29　　4.2.3 遺傳序列算法29</

15、p>　　4.2.4 蟻群算法30　　4.3 算法應(yīng)用31　　4.3.1 解決浙江旅行商問題時算法描述31　　4.3.2 蟻群算法的算法描述31　　4.3.3 蟻群算法解決浙江旅行商問題34<p&

16、gt;　　第5章最短路徑算法的展望36　　緒論38　　致謝39　　參考文獻(xiàn)40　　緒論<

17、/p>　　1.1 選題的意義及目的　　1.1.1 選題的意義　　隨著計算機(jī)科學(xué)的發(fā)展，人們生產(chǎn)生活經(jīng)濟(jì)利潤的提高，最短路徑問題逐漸成為計算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個研究熱點。也正因為最短路徑問題在實際生產(chǎn)生活中應(yīng)用廣泛，優(yōu)化該算法和提高算法的求解效率具有重大的現(xiàn)實意義。

18、;　　最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。算法具體的形式包括：確定起點的最短路徑問題—即已知起始結(jié)點，求最短路徑的問題；確定終點的最短路徑問題—與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題；在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題；確定起點終點的最短路徑問題—即已知起點和終點，求兩結(jié)點之間的最短路徑；

19、全局最短路徑問題—求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱作最短路徑算法。　　1.1.2 選題的目的　　本文研究目的在于收集整理關(guān)于最短路徑的普遍算法，為研究最短路徑問題在一些出行問題、管理問題、工程問題及實際生活問題中的應(yīng)用，為企業(yè)和個人提供方便的選擇方法。同時，也為參加數(shù)學(xué)建模的同學(xué)提供一些解題的思路與方法，為比賽提供有利的資源。最后應(yīng)

20、用蟻群算法來解決浙江旅行商問題。　　1.2 選題經(jīng)過及國內(nèi)外動態(tài)　　1.2.1 選題經(jīng)過　　二十世紀(jì)中后期，隨著計算機(jī)的出現(xiàn)和發(fā)展，圖論的研究得到廣泛重視，最短路徑問題是圖論中的一個典范問題，它已經(jīng)被應(yīng)用于眾多領(lǐng)域，如地理信息領(lǐng)域等?，F(xiàn)實生活中最短路徑的運(yùn)用非常多，算法也很多，最短路徑的分析是網(wǎng)絡(luò)分析最基本的功

21、能之一，近年來，隨著網(wǎng)絡(luò)的不斷發(fā)展，網(wǎng)絡(luò)中的最短路徑問題具有重大的理論意義和應(yīng)用價值。　　1.2.2 選題的國內(nèi)外動態(tài)　　最短路徑這一重要問題早在20世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時也有很多科學(xué)家研究這一問題的求解方法。但直到1959年荷蘭計算機(jī)科學(xué)家Edsger Wybe Dijkstra才給出這一問題求解的基本方思想，并給出了算法。當(dāng)時的Dij

22、kstra提出這一算法主要解決的問題是從固定的一個點到其他各點的最短路徑問題，后來這個算法就成了眾所周知的Dijkstra算法，也成了一代經(jīng)典。　　現(xiàn)如今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；第二類則是基于傳統(tǒng)人工智能理論的算法；第三類則是基于智能控制技術(shù)的算法。特別是近10年來，智能控制技術(shù)在路徑規(guī)劃問題中得到廣泛應(yīng)用，人們的研究興趣也逐漸從對前兩類的算法改進(jìn)轉(zhuǎn)

23、到了對第三類算法的進(jìn)一步研究。　　最短路徑算法的介紹　　Dijkstra 算法　　2.1.1 算法介紹及適用條件和范圍　　1.算法介紹　　Dijkstr

24、a(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標(biāo)號的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。

25、　　2.適用條件和范圍　?。?）單源最短路徑（從源點s到其它所有頂點v）；　?。?）有向圖和無向圖（無向圖可以看作，同屬于邊集E的有向圖）；　?。?）所有邊權(quán)非負(fù)（任取都有）。　　2.1.2

26、算法描述和算法實現(xiàn)　　1.算法描述　　如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路徑，則 v1→ v2→ v3 一定是 v1→ v3 的最短路徑。 v2→ v3→ v4 一定是 v2→ v4 的最短路徑。　　2.算法實現(xiàn)

27、;　　（1）初始化：dis[v]=maxint ；dis[s]=0；pre[s]=s;S={s}；　?。?）For i:=1 to n　?、偃-S中的一頂點u使得dis[u]=min{dis[v]|v∈V-S}　　②S=S

28、+{u}　?、跢or V-S中每個頂點v do Relax 　?。?）算法結(jié)束：dis[i]為s到i的最短距離；pre[i]為i的前驅(qū)節(jié)點。程序見參考文獻(xiàn)[8]。　　2.1.3 具體算法分析　　下圖中的有向圖，應(yīng)用Dij

29、kstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下表中。　　#include <iostream> 　　using namespace std; 　　const int maxnum = 100; 　　const int maxint = 99999

30、9; 　　// 各數(shù)組都從下標(biāo)1開始 　　int dist[maxnum]; // 表示當(dāng)前點到源點的最短路徑長度 　　int prev[maxnum]; // 記錄當(dāng)前點的前一個結(jié)點 　　int c[maxnum][maxnum]; // 記錄圖的兩點間路徑長度 <

31、;/p>　　int n, line; // 圖的結(jié)點數(shù)和路徑數(shù) 　　// n -- n nodes 　　// v -- the source node 　　// dist[ ] -- the distance from the ith node to the source node &

32、lt;/p>　　// prev[ ] -- the previous node of the ith node 　　// c[ ][ ] -- every two nodes' distance 　　void Dijkstra(int n, int v, int *dist, int *prev, int c[maxn

33、um][maxnum]) 　　{ 　　bool s[maxnum]; // 判斷是否已存入該點到S集合中 　　for(int i=1; i<=n; ++i) 　　{

34、　　dist[i] = c[v][i]; 　　s[i] = 0; // 初始都未用過該點 　　if(dist[i] == maxint) 　　prev[i] = 0; 　　else <p

35、>　　prev[i] = v; 　　} 　　dist[v] = 0; 　　s[v] = 1; 　　// 依次將未放入S集合的結(jié)點中，取dist[]最小值的結(jié)點，放入結(jié)合S中 　　// 一

36、旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度 　　// 注意是從第二個節(jié)點開始，第一個為源點 　　for(int i=2; i<=n; ++i) 　　{ 　　int tmp = maxint;

37、　　int u = v; 　　// 找出當(dāng)前未使用的點j的dist[j]最小值 　　for(int j=1; j<=n; ++j) 　　if((!s[j]) && dist[j]<tmp) <b&

38、gt;　　{ 　　u = j; // u保存當(dāng)前鄰接點中距離最小的點的號碼 　　tmp = dist[j]; 　　} 　　s[u] = 1; // 表示u點已存入S集合中

39、　　// 更新dist 　　for(int j=1; j<=n; ++j) 　　if((!s[j]) && c[u][j]<maxint) 　　{ 　　int newdist = dist[u] + c[u

40、][j]; 　　if(newdist < dist[j]) 　　{ 　　dist[j] = newdist; 　　prev[j] = u; 　　}

41、　　} 　　} 　　} 　　// 查找從源點v到終點u的路徑，并輸出 　　void searchPath(int *

42、prev,int v, int u) 　　{ 　　int que[maxnum]; 　　int tot = 1; 　　que[tot] = u; 　　tot++; </

43、b>　　int tmp = prev[u]; 　　while(tmp != v) 　　{ 　　que[tot] = tmp; 　　tot++; &l

44、t;/p>　　tmp = prev[tmp]; 　　} 　　que[tot] = v; 　　for(int i=tot; i>=1; --i) 　　if(i != 1) <

45、;p>　　cout << que[i] << " -> "; 　　else 　　cout << que[i] << endl; 　　}

46、　　int main() 　　{ 　　freopen("input.txt", "r", stdin); 　　// 各數(shù)組都從下標(biāo)1開始 　　// 輸入結(jié)點

47、數(shù) 　　cin >> n; 　　// 輸入路徑數(shù) 　　cin >> line; 　　int p, q, len; // 輸入p, q兩點及其路徑長度

48、;　　// 初始化c[][]為maxint 　　for(int i=1; i<=n; ++i) 　　for(int j=1; j<=n; ++j) 　　c[i][j] = maxint; 　　for(int i=1; i<=line; ++i) <

49、/p>　　{ 　　cin >> p >> q >> len; 　　if(len < c[p][q]) // 有重邊 　　{

50、　c[p][q] = len; // p指向q 　　c[q][p] = len; // q指向p，這樣表示無向圖 　　} 　　} 　　for(int i=1; i<=n; ++i) <

51、/p>　　dist[i] = maxint; 　　for(int i=1; i<=n; ++i) 　　{ 　　for(int j=1; j<=n; ++j) 　　printf("%8d

52、", c[i][j]); 　　printf("\n"); 　　} 　　Dijkstra(n, 1, dist, prev, c); 　　// 最短路徑長度 　　c

53、out << "源點到最后一個頂點的最短路徑長度: " << dist[n] << endl; 　　// 路徑 　　cout << "源點到最后一個頂點的路徑為: "; 　　searchP

54、ath(prev, 1, n); 　　} 　　輸入數(shù)據(jù): 　　5 　　7 &l

55、t;b>　　1 2 10 　　1 4 30 　　1 5 100 　　2 3 50 　　3 5 10 </b&

56、gt;　　4 3 20 　　4 5 60 　　輸出數(shù)據(jù): 　　999999 10 999999 30 100 　　1

57、0 999999 50 999999 999999 　　999999 50 999999 20 10 　　30 999999 20 999999 60 　　100 999999 10 60 999999　　2.2 A* 算法

58、2.2.1 算法介紹及適用條件和范圍　　1.算法介紹　　A*（A-Star）算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的方法；　　公式表示為： f(n)=g(n)+h(n), 　　其中f(n) 是從初始點經(jīng)由節(jié)點n到目標(biāo)點的估價函數(shù)，

59、　　g(n) 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價， 　　h(n)是從n到目標(biāo)節(jié)點最佳路徑的估計代價　　2.適用條件和范圍　　A*算法屬于一種啟發(fā)式搜索。它擴(kuò)展結(jié)點的次序類似于廣度優(yōu)先搜索，但不同的是每生成一個子結(jié)點需要計算估價

60、函數(shù)F，以估算起始結(jié)點到該結(jié)點的代價及它到達(dá)目標(biāo)結(jié)點的代價的和；每當(dāng)擴(kuò)展結(jié)點時，總是在所有待擴(kuò)展結(jié)點中選擇具有最小F值的結(jié)點作為擴(kuò)展對象，以便使搜索盡量沿最有希望的方向進(jìn)行。　　因此，A*算法只要求產(chǎn)生問題的全部狀態(tài)空間的部分結(jié)點，就可以求解問題了，搜索效率較高。　　確定估價函數(shù)方法通常是：搜索到該結(jié)點的深度+ 距離目標(biāo)最近的程度。

61、　　3.使用原理　　如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點的估價值）　　狀態(tài)空間圖　　搜索過程中設(shè)置兩個表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節(jié)點，CLOSE

62、D表中記錄已訪問過的節(jié)點。算法中有一步是根據(jù)估價函數(shù)重排OPEN表。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點。　　2.2.2 算法描述和算法實現(xiàn)　　算法描述及其實現(xiàn)　?。?）初始狀態(tài)：

63、　　OPEN=[A5];CLOSED=[];　?。?）估算A5，取得搜有子節(jié)點，并放入OPEN表中；　　OPEN=[B4, C4, D6]; CLOSED=[A5]　?。?）估算B4，取得搜有子節(jié)點，并放入OPEN表中；　　OPEN=[C4, E5, F5, D6]; C

64、LOSED=[B4, A5]　　（4）估算C4；取得搜有子節(jié)點，并放入OPEN表中；　　OPEN=[H3, G4, E5, F5, D6];CLOSED=[C4, B4, A5]　?。?）估算H3，取得搜有子節(jié)點，并放入OPEN表中；　　OPEN=[O2, P3, G4,

65、 E5, F5, D6]; CLOSED=H3C4, B4, A5]　?。?）估算O2，取得搜有子節(jié)點，并放入OPEN表中；　　OPEN=[P3, G4, E5, F5, D6]; CLOSED=[O2, H3, C4, B4, A5]　?。?）估算P3，已得到解。　　2

66、.2.3 具體算法分析　　在國際象棋的棋盤上，一匹馬共有8個可能的跳躍方向，求從起點到目標(biāo)點之間的最少跳躍次數(shù)。　　#include <iostream> #include <queue> using namespace std;&

67、#160; struct knight{ int x,y,step; int g,h,f; bool operator <

68、(const knight & k) const{ //重載比較運(yùn)算符 return f > k.f; }

69、;}k; bool visited[8][8];

70、; //已訪問標(biāo)記(關(guān)閉列表) int x1,y1,x2,y2,ans;

71、 //起點(x1,y1),終點(x2,y2),最少移動次數(shù)ans int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8個移動方向 priority_queue<knight> que;

72、60; 　　2.3 Bellman-Ford 算法　　2.3.1 算法介紹及適用條件和范圍　　1.算法介紹<p&

73、gt;　　Bellman-Ford算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點最短路徑問題。對于給定的帶權(quán)（有向或無向）圖 G=（V,E），其源點為s，加權(quán)函數(shù) w是邊集 E 的映射。對圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個布爾值，表明圖中是否存在著一個從源點s可達(dá)的負(fù)權(quán)回路。若不存在這樣的回路，算法將給出從源點s到圖G的任意頂點v的最短路徑d[v]。　　2.適

74、用條件和范圍　　（1）單源最短路徑(從源點s到其它所有頂點v)；　　（2）有向圖和無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)；　　（3）邊權(quán)可正可負(fù)(如有負(fù)權(quán)回路輸出錯誤提示)；　?。?）差分約束系統(tǒng)</

75、b>　　2.3.2 算法描述和算法實現(xiàn)　　1.算法描述　　1,.初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0; 　　2.迭代求解：反復(fù)對邊集E中的每條邊進(jìn)行松弛操作，使得頂點集V中的每個頂點

76、v的最短距離估計值逐步逼近其最短距離；（運(yùn)行|v|-1次） 　　3.檢驗負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解；否則算法返回true，并且從源點可達(dá)的頂點v的最短距離保存在 d[v]中。　　2.算法實現(xiàn)

77、（1）PASCA語言　　For i:=1 to |V|-1 do　　For 每條邊(u,v)∈E do　　Relax(u,v,w);　　For每條邊(u,v)∈E do　　If dis[u]+w<dis[v] Then Ex

78、it(False)　?。?）C/C++語言　　void bellman_ford(int v)　　{ for 1 to n　　initialize dist[v]; 　　for 2 to n-1 (i)&

79、lt;p>　　for 1 to n (j) 　　for 1 to n (k) 　　if edge[k][j] > 0 && dist[k] > edge[k][j]+dist[j]　　更新當(dāng)前值 }

80、　　2.3.3 具體算法設(shè)計　　typedef struct oo　　{　　int len,num;　　struct oo *next;　　} link;

81、;　　typedef struct　　{　　int num;　　link *next;　　} graph;</

82、p>　　/*　　node[]圖的鄰接表　　n節(jié)點總數(shù)　　s源點　　dis[]到源點的最短路徑長度<p

83、>　　pre[]最短路徑上的前驅(qū)結(jié)點　　算法返回true，當(dāng)且僅當(dāng)途中不包含從源點可達(dá)的負(fù)權(quán)回路　　*/　　bool bellmanFord(graph node[],int n,int s)　　{</b

84、>　　int dis[MAX],pre[MAX];　　int i,j;　　link *p;　　for(i=0;i<n;i++)

85、;　　{　　dis[i]=MAXVALUE;　　pre[i]=-1;　　}　　dis[s]=0;　　for(i=0;i<n;i+

86、+)　　{　　p=node[i].next;　　while(p)　　{　　if(p->len+dis[i]&l

87、t;dis[p->num])　　{dis[p->num]=p->len+dis[i];pre[p->num]=i;}　　p=p->next;　　}　　p=node[i].next;

88、　　while(p)　　{　　if(p->len+dis[i]<dis[p->num])　　return false;　　p=p->next;</p

89、>　　}　　}　　for(i=0;i<n;i++)　　{　　printf("%d %d\n",i,

90、dis[i]);　　j=i;　　while(j!=-1)　　{　　printf("%d ",j);　　j=pr

91、e[j];　　}　　cout<<endl;　　}　　return true;　　}&

92、lt;/p>　　//這個是鄰接矩陣　　const int MAX = 100;　　const int MAXVALUE = 1000;　　int graph[MAX][MAX],n;　　/

93、*　　graph[][]圖的鄰接陣　　n 圖的節(jié)點數(shù)　　s 源點　　dis[] 存放最短路徑　　pre[] 存放最短路徑上的前驅(qū)節(jié)點&

94、lt;/p>　　算法返回true，當(dāng)且僅當(dāng)途中不包含從源點可達(dá)的負(fù)權(quán)回路，并輸出每個節(jié)點最短路徑的前驅(qū)值　　*/　　bool bellmanFord(int graph[][MAX],int n,int s)　　{</b&g

95、t;　　int dis[MAX],pre[MAX];　　int i,j,k;　　for(i=0;i<n;i++)　　{　　dis[i]=MAXVALUE;<

96、p>　　pre[i]=-1;　　}　　dis[s]=0;　　for(i=0;i<n;i++)　　{　　f

97、or(j=0;j<n;j++)　　if(i!=j&&dis[j]>dis[i]+graph[i][j])　　{　　dis[j]=dis[i]+graph[i][j];　　pre[j]=i;

98、　　}　　for(j=0;j<n;j++)　　if(i!=j&&dis[j]>dis[i]+graph[i][j])　　return false;

99、;　　}　　for(i=0;i<n;i++)　　{　　printf("%d %d\n",i,dis[i]);　　k=i;</b&g

100、t;　　while(pre[k]!=-1)　　{　　printf("%d ",pre[k]);　　k=pre[k];<b&

101、gt;　　}　　cout<<endl;　　}　　return true;　　}　　2.4 Topological Sor

102、t 算法　　2.4.1 算法介紹及適用條件和范圍　　1.算法介紹　　Topological Sort（拓?fù)渑判颍┧惴ㄊ嵌x在有向圖中的一種操作，目的是根據(jù)結(jié)點間的關(guān)系求的節(jié)點的一個線性排列（這點與遍歷操作的目的相似）。這種操作在有關(guān)工程進(jìn)度/次序規(guī)劃之類問題中有著大量的應(yīng)用

103、。一般的大型工程，都可劃分為多個工序/步驟/子工程，這些工序有的可以獨(dú)立進(jìn)行，但大多數(shù)和其他工序關(guān)聯(lián)，即某工序的進(jìn)行，要等到其他一些工序的完成才能開始，這類問題都可歸結(jié)到拓?fù)渑判颉?lt;/p>　　2.使用條件和范圍　?。?）AOV網(wǎng)(Activity On Vertex Network)；</

104、p>　?。?）有向圖；　?。?）作為某些算法的預(yù)處理過程(如DP)。　　2.4.2 算法描述和算法實現(xiàn)　　1.算法描述　　（1）每次挑選入度為0的頂點輸出(不計次序)

105、；　?。?）如果最后發(fā)現(xiàn)輸出的頂點數(shù)小于|V|，則表明有回路存在。　　2.算法實現(xiàn)　?。?）數(shù)據(jù)結(jié)構(gòu)：adj:鄰接表;有4個域{u,v,w,next}；　　indgr[i]:頂點i的入度；

106、stack[]:棧；　?。?）初始化:top=0 (棧頂指針)；　?。?）將初始狀態(tài)所有入度為0的頂點壓棧；　?。?）I=0 (計數(shù)器)；　?。?）While棧非空(top>0) do　?、夙旤c

107、v出棧；輸出v；計數(shù)器增1；　?、贔or與v鄰接的頂點u do　　a. dec(indgr[u])；　　b. If indgr[u]=0 then頂點u入棧；　　（6）EXIT(I=|V|)。<

108、;p>　　2.4.3 具體算法設(shè)計　　#define MAXV 30　　#define OK 1　　#define ERROR 0　　typedef char VertexType;

109、;　　typedef int status;　　typedef struct ArcNode{　　int adjvex;　　struct ArcNode *nextarc;　　}ArcNode;

110、;　　typedef struct VNode{　　VertexType data;　　ArcNode *firstarc;　　}VNode,AdjList[MAXV ];　　typedef struct{　　AdjList ve

111、rtices;　　int vexnum,arcnum;　　}ALGraph;　　int LocateVex(ALGraph G,char m);　　status Creat_Graph1(ALGraph &G);</p&

112、gt;　　int dfs_topsort(ALGraph g,int n);//拓?fù)渑判蛩惴?lt;/p>　　void dfs(ALGraph g,int v,int&flag);//深度優(yōu)先搜索　　void Menuselect();　　頭文件</p&

113、gt;　　#include<stdio.h>　　#include<malloc.h>　　#include<stdlib.h>　　#include<iostream.h>　　#include"h

114、ead.h"　　int visited[MAXV];　　int finished[MAXV];　　int dfs_topsort(ALGraph g,int n)　　{ 　　int

115、flag=1,i;　　for(i=0;i<n;i++) //置初值　　{　　visited[i]=0;　　finished[i]=1;　　}&

116、lt;/p>　　i=0; //從編號為0的頂點開始遍歷　　while(flag&&i<n)　　{　　if(visited[i]==0)　　{ i++;&

117、lt;/b>　　dfs(g,i,flag);}　　}　　return flag;　　}　　void dfs(ALGraph g,int v,int&

118、amp;flag)　　{　　ArcNode *p;　　printf("%d\n",v);　　finished[v]=0;　　visited[v]=0;

119、　　p=g.vertices[v]. firstarc; //找頂點V的第一條弧　　while(p!=NULL)　　{　　if(visited[p->adjvex]==0)　　{</b

120、>　　dfs(g,p->adjvex,flag);　　finished[p->adjvex ]=1;　　}　　p=p->nextarc ;　　}<

121、;/b>　　}　　int LocateVex(ALGraph G,char m){　　int i;　　for(i=0;i<G.vexnum;i++)<p&

122、gt;　　if(G.vertices[i].data==m)return i;　　return ERROR;　　}　　status Creat_Graph1(ALGraph &G){　　int i,j,r;char m,n;A

123、rcNode *p;　　printf("請輸入頂點數(shù)：");　　scanf("%d",&G.vexnum);　　printf("請輸入邊數(shù)：");　　scanf("%d",&G

124、.arcnum);　　printf("請輸入圖的所有頂點：");　　for(i=0;i<G.vexnum;i++)　　{cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}

125、printf("請輸入圖的所有邊，如A->B邊記為AB，：\n");　　for(r=0;r<G.arcnum;r++){　　cin>>m;cin>>n;　　i=LocateVex(G,m);j=LocateVex(G,n);<p

126、>　　p=(ArcNode*)malloc(sizeof(ArcNode));　　p->adjvex=j;　　p->nextarc=G.vertices[i].firstarc;　　G.vertices[i].firstarc=p;

127、}　　return OK;　　} 　　void Menuselect(){　　int done=1,select,i;　　ALGraph g;<

128、;p>　　printf("please input select number");　　while(done){　　printf("請輸入操作碼：");　　scanf("%d",&select);

129、　switch(select){　　case 1: 　　if(Creat_Graph1(g))printf("OK");　　printf("\n\n");　　break;<

130、;/b>　　case 2:　　dfs_topsort( g,g.vexnum);　　printf("\n\n");　　break;

131、;　　case 3:　　done=0;　　break;　　default:printf("輸入的操作碼錯誤\n\n");

132、　　}　　}　　}　　實現(xiàn)文件　　#include<stdio.h>　　#inclu

133、de<malloc.h>　　#include<stdlib.h>　　#include<iostream.h>　　#include"head.h"　　void main()&l

134、t;b>　　{ 　　printf("圖的拓?fù)渑判?quot;);　　Menuselect();　　}　　2.5 SSSP On DAG 算法　　2.5.1

135、算法介紹及適用條件和范圍　　適用條件和范圍　?。?）DAG(Directed Acyclic Graph,有向無環(huán)圖)；　?。?）邊權(quán)可正可負(fù)。　　2.5.2 算法描述和算法實現(xiàn)<

136、;p>　　1.算法描述　?。?）Toposort；　　（2）If Toposort=False Then HALT(Not a DAG)；　?。?）For拓?fù)湫虻拿總€頂點u do<

137、p>　　For u的每個鄰接點v do　　Relax(u,v,w)；　?。?）算法結(jié)束后：如有環(huán)則輸出錯誤信息；否則dis[i]為s到i的最短距離，pre[i]為前驅(qū)頂點。　　2.算法實現(xiàn)　　此算法時間復(fù)雜度

138、O(V+E)，時間和編程復(fù)雜度低，如遇到符合條件的題目(DAG)，推薦使用。還有，此算法的步驟（3）可以在toposort中實現(xiàn)，這樣即減小了此算法復(fù)雜度的一個系數(shù)。　　2.6 Floyd 算法　　2.6.1 算法介紹及適用條件和范圍　　1.算法介紹

139、　　通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。 　　從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離

140、矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。　　2.適用條件和范圍　?。?）APSP(All Pairs Shortest Paths)；　?。?）稠密圖效果最佳；　?。?）邊權(quán)可正

141、可負(fù)。　　2.6.2 算法描述和算法實現(xiàn)　　算法描述　?。?）初始化：dis[u,v]=w[u,v]。　?。?）For k=1 to n　　For i

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最短路徑算法的研究畢業(yè)設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

最短路徑算法的研究畢業(yè)設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載