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

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

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

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

4、法；最短路徑應(yīng)用；蟻群算法；浙江旅行商</p><p><b>　　Abstract</b></p><p>　　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</p><p>　　Key words：The shortest path algorithm, The sh

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、;</p><p>　　（1）初始化：dis[v]=maxint ；dis[s]=0；pre[s]=s;S={s}；</p><p>　　（2）For i:=1 to n</p><p>　?、偃-S中的一頂點(diǎn)u使得dis[u]=min{dis[v]|v∈V-S}</p><p><b>　?、赟=S

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

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

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

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

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

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

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

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

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

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

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

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

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

41、</p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　// 查找從源點(diǎn)v到終點(diǎn)u的路徑，并輸出 </p><p>　　void searchPath(int *

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

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

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

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

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

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

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

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

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

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

52、", c[i][j]); </p><p>　　printf("\n"); </p><p><b>　　} </b></p><p>　　Dijkstra(n, 1, dist, prev, c); </p><p>　　// 最短路徑長(zhǎng)度 </p><p>　　c

53、out << "源點(diǎn)到最后一個(gè)頂點(diǎn)的最短路徑長(zhǎng)度: " << dist[n] << endl; </p><p><b>　　// 路徑 </b></p><p>　　cout << "源點(diǎn)到最后一個(gè)頂點(diǎn)的路徑為: "; </p><p>　　searchP

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

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

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

57、0 999999 50 999999 999999 </p><p>　　999999 50 999999 20 10 </p><p>　　30 999999 20 999999 60 </p><p>　　100 999999 10 60 999999</p><p>　　2.2 A* 算法</p><p>　　

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

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

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

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

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

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

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

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

66、.2.3 具體算法分析</p><p>　　在國(guó)際象棋的棋盤上，一匹馬共有8個(gè)可能的跳躍方向，求從起點(diǎn)到目標(biāo)點(diǎn)之間的最少跳躍次數(shù)。</p><p>　　#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、   //起點(diǎn)(x1,y1),終點(diǎn)(x2,y2),最少移動(dòng)次數(shù)ans int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8個(gè)移動(dòng)方向 priority_queue<knight> que;     

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

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

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

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

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

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

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

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

80、　　2.3.3 具體算法設(shè)計(jì)</p><p>　　typedef struct oo</p><p><b>　　{</b></p><p>　　int len,num;</p><p>　　struct oo *next;</p><p><b>　　} link;</b>

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

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

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

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

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

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

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

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

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

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

91、e[j];</b></p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b>&

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

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

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

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

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

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

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

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

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

101、gt;　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　2.4 Topological Sor

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

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

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

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

106、stack[]:棧；</p><p>　　（2）初始化:top=0 (棧頂指針)；</p><p>　?。?）將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧；</p><p>　　（4）I=0 (計(jì)數(shù)器)；</p><p>　?。?）While棧非空(top>0) do</p><p>　　①頂點(diǎn)

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

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

109、;　　typedef int status;</p><p>　　typedef struct ArcNode{</p><p>　　int adjvex;</p><p>　　struct ArcNode *nextarc;</p><p><b>　　}ArcNode;</b></p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

123、rcNode *p;</p><p>　　printf("請(qǐng)輸入頂點(diǎn)數(shù)：");</p><p>　　scanf("%d",&G.vexnum);</p><p>　　printf("請(qǐng)輸入邊數(shù)：");</p><p>　　scanf("%d",&G

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

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

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

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

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

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

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

131、;<b>　　case 3:</b></p><p><b>　　done=0;</b></p><p><b>　　break;</b></p><p>　　default:printf("輸入的操作碼錯(cuò)誤\n\n");</p><p><b>

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

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

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

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

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

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

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

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

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

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