數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告五最短路徑

1、實(shí)驗(yàn)課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)?？瓢鄬W(xué)生名稱學(xué)號(hào)指導(dǎo)教師2012-2013學(xué)年第一學(xué)期1-9周目錄一、概述：21.1問(wèn)題說(shuō)明21.2系統(tǒng)實(shí)現(xiàn)的目標(biāo)21.3系統(tǒng)實(shí)施方案2二、系統(tǒng)分析：32.1設(shè)計(jì)理念32.2設(shè)計(jì)要求32.3需求分析32.4算法說(shuō)明4三、大綱設(shè)計(jì)：63.1程序流程圖7四、詳細(xì)設(shè)計(jì)：84.1圖中的存儲(chǔ)結(jié)構(gòu)設(shè)置84.2單一來(lái)源最短路徑84.3頂點(diǎn)對(duì)之間的最短路徑94.4構(gòu)造有向圖的存儲(chǔ)結(jié)構(gòu)104.5第納爾算法104.6弗洛伊德算法114.7運(yùn)行主節(jié)目12五、操作和測(cè)試：13六：總結(jié)和經(jīng)驗(yàn)15附錄：節(jié)目代碼15一、概述：1.1問(wèn)題說(shuō)明交通網(wǎng)絡(luò)牙齒很發(fā)達(dá)，交通工具和交通方式牙齒不斷更新的今

2、天，人們出差、旅行或其他旅行時(shí)，不僅節(jié)約交通費(fèi)用，還對(duì)里程和必要的時(shí)間等感興趣的牙齒。對(duì)于這些人關(guān)心的問(wèn)題，可以使用圖片結(jié)構(gòu)表示交通網(wǎng)絡(luò)系統(tǒng)，使用計(jì)算機(jī)構(gòu)建交通咨詢系統(tǒng)。圖中的頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。牙齒交通系統(tǒng)可以回答旅客提出的各種路徑選擇問(wèn)題。例如，問(wèn)題之一是：“從a點(diǎn)到b點(diǎn)的旅客想選擇途中中轉(zhuǎn)次數(shù)最少的路線?！奔僭O(shè)圖中的每個(gè)站都要換車，牙齒問(wèn)題是找到從頂點(diǎn)a到頂點(diǎn)b包含的邊數(shù)最小的路徑。我們只需從頂點(diǎn)a開(kāi)始，廣度優(yōu)先搜索作畫。一旦遇到頂點(diǎn)b就終止。(阿爾伯特愛(ài)因斯坦，northern exposure(美國(guó)電視電視劇)，作品)結(jié)果，從樹(shù)、根頂點(diǎn)a老師到頂點(diǎn)b的路徑是最少的

3、傳輸路徑。路徑中a和b之間的頂點(diǎn)是路徑的中繼點(diǎn)，但只是最簡(jiǎn)單圖形的最短路徑問(wèn)題。系統(tǒng)還可以回答這樣的路徑選擇問(wèn)題。1.2系統(tǒng)實(shí)現(xiàn)的目標(biāo)通過(guò)課程設(shè)計(jì)，了解和初步了解實(shí)現(xiàn)設(shè)計(jì)、大型系統(tǒng)的整個(gè)過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、調(diào)試分析、數(shù)據(jù)結(jié)構(gòu)選擇、設(shè)計(jì)、實(shí)施和操作方法的掌握，為進(jìn)一步的應(yīng)用程序開(kāi)發(fā)奠定了基礎(chǔ)。應(yīng)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)編寫解決指定問(wèn)題的程序。1.3系統(tǒng)實(shí)施方案首先，決定系統(tǒng)要達(dá)到什么目的，為了達(dá)到這種目的，首先要實(shí)現(xiàn)的程序。這是關(guān)鍵部分。劃分模塊、源代碼、牙齒程序大致分為6個(gè)模塊，由主函數(shù)組和5個(gè)自定義函數(shù)組組成。然后進(jìn)行機(jī)器調(diào)試，協(xié)調(diào)幾個(gè)

4、大模塊，組成完全實(shí)現(xiàn)其功能的程序，最后提交設(shè)計(jì)報(bào)告。二、系統(tǒng)分析：2.1設(shè)計(jì)理念利用鄰接矩陣存儲(chǔ)與交通網(wǎng)絡(luò)地圖的信息，利用迪塞斯特拉算法實(shí)現(xiàn)地圖單一來(lái)源最短路問(wèn)題，然后利用斐洛算法實(shí)現(xiàn)圖片中任何一對(duì)頂點(diǎn)之間的最短路問(wèn)題，從而實(shí)現(xiàn)旅客需要咨詢的問(wèn)題。2.2設(shè)計(jì)要求牙齒交通咨詢系統(tǒng)必須完成城市網(wǎng)絡(luò)地圖的存儲(chǔ)，實(shí)現(xiàn)從任意城市頂點(diǎn)到其他城市頂點(diǎn)的最短路徑問(wèn)題，還必須實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。因此，設(shè)計(jì)必須分為三個(gè)部分。一是構(gòu)建交通網(wǎng)絡(luò)地圖的存儲(chǔ)結(jié)構(gòu)。二是解決單一源路徑問(wèn)題。最后實(shí)現(xiàn)兩個(gè)城市之間的最短路徑問(wèn)題。設(shè)計(jì)要求：1.構(gòu)建交通網(wǎng)絡(luò)網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu)。整體設(shè)計(jì)需要繪制流程圖。3.供應(yīng)商程序測(cè)試

5、節(jié)目。4.界面很熟悉。2.3需求分析根據(jù)需要，在系統(tǒng)中創(chuàng)建無(wú)向圖。系統(tǒng)必須靈活，用戶可以根據(jù)當(dāng)前交通網(wǎng)絡(luò)圖輸入和更改初始數(shù)據(jù)。系統(tǒng)基于用戶的輸入構(gòu)建了無(wú)向圖的結(jié)構(gòu)，通過(guò)dickstra算法和弗洛伊德算法實(shí)現(xiàn)了需求，并提供了兩種茄子功能供用戶選擇。2.4算法說(shuō)明輸入城市和公路數(shù)據(jù)查詢從一個(gè)城市到另一個(gè)城市的最短路徑基于無(wú)向圖生成查詢功能結(jié)構(gòu)建設(shè)教父相通網(wǎng)絡(luò)交通祖懷系統(tǒng)字典城市之間的距離查詢兩個(gè)城市之間的最短路徑迪克斯特拉算法特定流程圖開(kāi)始初始化距離和路徑i=1j=1；j；jn弗洛伊德算法特定流程圖開(kāi)始初始化距離和路徑從到的最短路徑長(zhǎng)度，其中只有集中的節(jié)點(diǎn)設(shè)置為中間節(jié)點(diǎn)輸出結(jié)果最短路徑通過(guò)點(diǎn)k最短

6、路徑不通過(guò)點(diǎn)k三、大綱設(shè)計(jì)：程序包含兩種茄子抽象數(shù)據(jù)類型。一個(gè)是圖形，另一個(gè)是隊(duì)列。1、設(shè)置“圖片”抽象數(shù)據(jù)類型定義。adt graph數(shù)據(jù)對(duì)象v: v是具有相同屬性(稱為頂點(diǎn)集)的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系r:r=vrvr=v，w | v，w-vp(v，w)，v，w表示從v到w的圓弧。謂詞p(v，w)定義了圓弧v，w的含義或信息。默認(rèn)操作p:creategraph(g，v，vr)；初始條件：v是圖形的頂點(diǎn)集，vr是圖形中弧的集合。任務(wù)結(jié)果：按照v和vr定義構(gòu)建圖表。locatevex(g，u):初始條件：圖g存在，u和g的頂點(diǎn)具有相同的特征。操作結(jié)果：如果g具有頂點(diǎn)u，則地物返回該頂點(diǎn)的位置。

7、否則，將返回其他信息。first_next_adj(g，v)；初始條件：圖g存在，v是g的頂點(diǎn)。操作結(jié)果：返回v的第一個(gè)相鄰頂點(diǎn)。如果g沒(méi)有相鄰頂點(diǎn)，則返回null。dfstraverse(g，i):初始條件：圖g存在，i是鄰接矩陣中頂點(diǎn)的位置。作業(yè)結(jié)果：從i開(kāi)始，先遍歷圖形的深度。bfstraverse(g，i):初始條件：圖g存在，i是鄰接矩陣中頂點(diǎn)的位置。作業(yè)結(jié)果：從i開(kāi)始，先遍歷圖片的寬度。 adtgraph2、設(shè)置隊(duì)列的抽象數(shù)據(jù)類型定義。adt queue數(shù)據(jù)對(duì)象：d= a i a i數(shù)據(jù)關(guān)系：r1=a i，a i1 | a i1，a id，i=2，n規(guī)則a1結(jié)尾是隊(duì)列標(biāo)頭，a n結(jié)

8、尾是隊(duì)列結(jié)尾?；救蝿?wù)：initqueue(q)任務(wù)結(jié)果：配置空隊(duì)列q。enqueue(q，e)初始條件：隊(duì)列q已存在。任務(wù)結(jié)果：插入元素e為q的新團(tuán)隊(duì)尾部元素dequeue(q)初始條件：隊(duì)列q已存在。任務(wù)結(jié)果：刪除q的相對(duì)元素并返回值。queueempty(q)初始條件：隊(duì)列q已存在。任務(wù)結(jié)果：如果q為空隊(duì)列，則返回1，否則返回0。queuelenghth(q)初始條件：隊(duì)列q已存在。操作結(jié)果：返回q的元素?cái)?shù)，即隊(duì)列長(zhǎng)度。gethead(q，e)初始條件：q是非空隊(duì)列。工作結(jié)果：使用e返回q的對(duì)手元素。 adt queue3、牙齒程序包含三個(gè)茄子模塊。1)主節(jié)目模塊void main()選

9、擇要?jiǎng)?chuàng)建的圖表的類型。請(qǐng)創(chuàng)建圖表并以鄰接矩陣格式打印。找到地物的深度和廣度優(yōu)先搜索以及頂點(diǎn)的第一個(gè)相鄰點(diǎn)。查找從一個(gè)源點(diǎn)到其馀頂點(diǎn)的最短路徑。2)圖形模塊實(shí)現(xiàn)圖的抽象數(shù)據(jù)類型和基本操作3)隊(duì)列模塊實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型和當(dāng)前操作3.1程序流程圖四、詳細(xì)設(shè)計(jì)：設(shè)置4.1圖形的存儲(chǔ)結(jié)構(gòu)首先定義交通地圖的存儲(chǔ)結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。g=(v，e)是具有n個(gè)頂點(diǎn)的圖形，g的鄰接矩陣是n階方陣，定義如下：ai，j=鄰接矩陣列標(biāo)頭，當(dāng)欄標(biāo)頭順序一致時(shí)，插圖的鄰接矩陣表現(xiàn)法是唯一的。根據(jù)圖的鄰接矩陣表示，除了將頂點(diǎn)之間的相鄰關(guān)系存儲(chǔ)為二維陣列的鄰接矩陣外，通常還需要使用n個(gè)元素一維

10、陣列存儲(chǔ)頂點(diǎn)信息。其中下標(biāo)是i的元素存儲(chǔ)頂點(diǎn)i的信息。因此，圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下：#definf mvnum 88 /最大頂點(diǎn)數(shù)typedef structvertex type vexsmv num；/vertex陣列，假設(shè)為char類型adj matrix arcsmv nummv num；/鄰接矩陣，假設(shè)為int類型 mgraph4.2單一來(lái)源最短路徑對(duì)最短路徑的提法很多。這里首先介紹單個(gè)源最短路問(wèn)題，即乳香度(卷權(quán))。我想查找從源點(diǎn)sv到g其馀頂點(diǎn)的最短路徑。為了便于敘述，我們將路徑的起點(diǎn)稱為源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)稱為終點(diǎn)。(約翰肯尼迪，美國(guó)電視電視劇)那么，如何得到給定方向

11、性圖的單個(gè)源最短路徑呢？dijkstra提出了隨著路徑長(zhǎng)度增加點(diǎn)的最短路徑算法，即dijkstra算法。dijestra算法追求最短路徑實(shí)現(xiàn)。g=(v，e)是直接圖形，節(jié)點(diǎn)集，cost是表示g的鄰接矩陣，costij表示轉(zhuǎn)向權(quán)。如果沒(méi)有方向邊，則costij的權(quán)重為無(wú)窮大，此處為32767。s是每個(gè)元素代表一個(gè)頂點(diǎn)的集合，從源到牙齒頂點(diǎn)的最短距離已經(jīng)被求出。將頂點(diǎn)v1設(shè)置為源點(diǎn)，并且集合s的初始狀態(tài)僅包含一個(gè)元素，頂點(diǎn)v1。陣列dist記錄從源點(diǎn)到其他頂點(diǎn)的當(dāng)前最短距離。初始值為dist i=cost v1 i，i=1，2，n。在非s頂點(diǎn)集v-s中，選擇頂點(diǎn)w以最小化distw的值。因此，僅通

12、過(guò)源點(diǎn)到w之間s的頂點(diǎn)，向集合s添加w，并調(diào)整dist中記錄的源點(diǎn)到v-s中每個(gè)頂點(diǎn)v的距離。在原始distv和distw costwv中，選擇較小的值作為新dist。重復(fù)以上過(guò)程，直到v-s為空。結(jié)果s記錄從源點(diǎn)到其頂點(diǎn)的最短路徑的頂點(diǎn)集合，陣列dist記錄從源點(diǎn)到v中其馀頂點(diǎn)的最短路徑，path是最短路徑的路徑陣列。其中pathi表示從源點(diǎn)到頂點(diǎn)i的最短路徑上的前導(dǎo)頂點(diǎn)。因此，dijestra算法可用的自然語(yǔ)言如下：初始化s和d，清空最短路徑端點(diǎn)集，并設(shè)置初始最短路徑值。sv1=true；dv1=0；/s集最初僅包含源點(diǎn)，從源點(diǎn)到源點(diǎn)的距離為零。while (s集中的頂點(diǎn)數(shù)及其是否存在)。

13、如果有，比較和vi，v1，vj的路徑長(zhǎng)度，長(zhǎng)度短是當(dāng)前求的最短路徑。牙齒路徑是中間頂點(diǎn)序列號(hào)不大于1的最短路徑。其次，考慮從vi到vj是否包含頂點(diǎn)v2為中間頂點(diǎn)的路徑。否則，從vi到vj的當(dāng)前最短路徑是在前面的步驟中獲得的。如果存在，可以使用和分割。牙齒兩條路徑是以前找到的中間頂點(diǎn)序列號(hào)不大于1的最短路徑，加上兩條路徑長(zhǎng)度即可得出路徑長(zhǎng)度。將牙齒長(zhǎng)度與從vi到vj的中間頂點(diǎn)編號(hào)不大于1的最短路徑進(jìn)行比較，使用較短的當(dāng)前vi到vj的中間頂點(diǎn)編號(hào)不大于2的最短路徑。以這種方式添加頂點(diǎn)vn牙齒從當(dāng)前vi到vj的最短路徑，然后選擇從vi到vj的中間頂點(diǎn)編號(hào)不大于n的最短路徑。圖g中的頂點(diǎn)編號(hào)不大于n，因此從vi到vj的中間頂點(diǎn)編號(hào)不大于n的最短路徑，并且考慮到所有頂點(diǎn)都可能是中間頂點(diǎn)，因此是從vi到vj的最短路徑。4.4構(gòu)造有向圖的存儲(chǔ)結(jié)構(gòu)void createmgraph (mgraph * g，int n，int e)int i、j、k、w；for(i=1)；i=n；i)g-vexsi=(char)i；for(i=1)；i=n；i)for(j=1)；j=n；j)g-arcsij=max int；printf(輸