數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-Floyd算法求解最短路徑

(一)紙張與頁(yè)面要求(1)題目介紹和功能要求(或描述)(2)系統(tǒng)功能模塊結(jié)構(gòu)圖(4)涉及到的函數(shù)的描述；(5)主要算法描述(程序流程圖)(7)課程設(shè)計(jì)的總結(jié)及體會(huì)(8)參考文獻(xiàn)最短路徑院(系):計(jì)算機(jī)學(xué)院指導(dǎo)教師評(píng)語(yǔ)：I本人聲明：所呈交的報(bào)告(含電子版及數(shù)據(jù)文件)是我個(gè)人在導(dǎo)師指導(dǎo)下獨(dú)立進(jìn)行設(shè)計(jì)工作及取得的研究結(jié)果。盡我所知，除了文中特別加以標(biāo)注或致謝中所羅列的內(nèi)容以外，報(bào)告中不包含其他人己經(jīng)發(fā)表或撰寫過(guò)的研究結(jié)果，也不包含其它教育機(jī)構(gòu)使用過(guò)的材料。與我一同工作的同學(xué)對(duì)本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的說(shuō)明并表示了謝意。報(bào)告資料及實(shí)驗(yàn)數(shù)據(jù)若有不實(shí)之處，本人愿意接受本教學(xué)環(huán)節(jié)“不及格”和“重修或重做”的評(píng)分結(jié)論并承擔(dān)相關(guān)一切后Ⅱ課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)名稱專業(yè)(物聯(lián)網(wǎng)方向)學(xué)生姓名孫思班級(jí)學(xué)號(hào)題目名稱起止日期課設(shè)內(nèi)容和要求：給出一張無(wú)向圖，圖上每一個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市之間存在路徑，邊上的權(quán)值表示城市間的路經(jīng)長(zhǎng)度。利用弗洛伊德(Floyd)算法求解最短路徑求解任意兩個(gè)城市之間的最短路徑問題。參考資料：《算法與數(shù)據(jù)結(jié)構(gòu)》《C語(yǔ)言程序設(shè)計(jì)》教研室審核意見：教研室主任簽字：指導(dǎo)教師(簽名)年月日沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告學(xué)生(簽名)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 2 3 3 4 5第三章使用說(shuō)明 9 附錄(關(guān)鍵部分程序清單) 1給出一張無(wú)向圖，圖上每一個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市之間存在路徑，邊上的權(quán)值表示城市間的路經(jīng)長(zhǎng)度。利用弗洛伊德(Floyd)算法求解最短路徑求解任意兩個(gè)城市之間的最短路徑問題。將問題分解為三個(gè)方面，第一個(gè)方面是對(duì)于無(wú)向圖的存儲(chǔ)問題，第二個(gè)方面是實(shí)現(xiàn)弗洛伊德(Floyd)算法求解最短路徑，第三個(gè)方面是將最短路徑輸出。首先對(duì)于圖的建立選擇合適的存儲(chǔ)結(jié)構(gòu)，考慮到之后要用的弗洛伊德算法所以選擇采用鄰接矩陣存儲(chǔ)無(wú)向圖。然后采用弗洛伊德算法，該算法又叫插點(diǎn)法。是利用三重循環(huán)產(chǎn)生一個(gè)存儲(chǔ)每個(gè)結(jié)點(diǎn)最短距離的矩陣，基本思想是設(shè)置一個(gè)n階矩陣權(quán)值作為路徑長(zhǎng)度，無(wú)邊連接記做無(wú)窮，多次循環(huán)，向原路徑加入新的頂點(diǎn)，若增加的頂點(diǎn)使得路徑比原路徑短，則用新路徑代替原始路徑，將頂點(diǎn)信息存儲(chǔ)在環(huán)執(zhí)行完畢最短路徑的信息存儲(chǔ)在兩個(gè)數(shù)組中。最后將最短路徑的信息輸出。2一個(gè)無(wú)向圖用每個(gè)頂點(diǎn)代表城市，頂點(diǎn)之間邊的權(quán)重表示城市之間的路徑，將頂點(diǎn)信息和邊的信息輸入程序，即可得到每?jī)蓚€(gè)城市之間的最短路徑長(zhǎng)度值以及這條路徑經(jīng)過(guò)的城市?？梢詾榻ㄖ穯栴}提供參考。設(shè)計(jì)環(huán)境：(1)WINDOWS7系統(tǒng)3主函數(shù)輸出最短路徑信息調(diào)用弗洛伊德算法輸入無(wú)向圖頂點(diǎn)及權(quán)值主函數(shù)輸出最短路徑信息調(diào)用弗洛伊德算法輸入無(wú)向圖頂點(diǎn)及權(quán)值第二章程序設(shè)計(jì)4Find:根據(jù)名稱得到指定頂點(diǎn)在頂點(diǎn)集合中的下標(biāo)，利用此函數(shù)找到頂點(diǎn)所在位Create:創(chuàng)建無(wú)向圖的鄰接矩陣，因?yàn)槊織l邊都有權(quán)值，創(chuàng)建的是無(wú)向網(wǎng)的鄰接矩陣，用權(quán)值代替1,沒有邊連接則為無(wú)窮。向原路徑加入新的頂點(diǎn)，若增加的頂點(diǎn)使得路徑比原路徑短，則用新路徑代替原徑經(jīng)過(guò)的所有頂點(diǎn)。三重循環(huán)執(zhí)行完畢最短路徑的信息存儲(chǔ)在兩個(gè)數(shù)組中。主函數(shù)：在主函數(shù)里定義一個(gè)無(wú)向圖，一個(gè)三維矩陣p,二維矩陣D,對(duì)各個(gè)數(shù)進(jìn)行調(diào)用，實(shí)現(xiàn)無(wú)向網(wǎng)的建立，運(yùn)用弗洛伊德算法求解出最短路徑，將路徑長(zhǎng)5開始NYNYNY記錄相對(duì)路徑和權(quán)重結(jié)束沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告6NYNY結(jié)束78結(jié)束9第三章使用說(shuō)明1.將頂點(diǎn)數(shù)和邊數(shù)輸出，中間用空格隔開。圖3.1.12.輸入頂點(diǎn)信息。請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：44請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：44圖3.1.23.依次輸入每條邊連接的兩個(gè)頂點(diǎn)用空格間隔，邊的權(quán)值。請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：44請(qǐng)輸入與第1條邊相連的兩條邊v1請(qǐng)輸入該邊的權(quán)重：1請(qǐng)輸入該邊的權(quán)重：2請(qǐng)輸入該邊的權(quán)重：3bcdd4.得到每?jī)蓚€(gè)頂點(diǎn)城市間的最短距離以及經(jīng)過(guò)的城市。入入4第四章程序測(cè)試請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：44了請(qǐng)輸入該邊的權(quán)重：1請(qǐng)謂請(qǐng)請(qǐng)謂請(qǐng)到。經(jīng)過(guò)的頂點(diǎn)有：ab最短路徑長(zhǎng)度為：1到到到到b最短路徑長(zhǎng)度為：1c最短路徑長(zhǎng)度為：2cd最短路徑長(zhǎng)度為：5c最短路徑長(zhǎng)度為：2d最短路徑長(zhǎng)度為：3cd最短路徑長(zhǎng)度為：5d最短路徑長(zhǎng)度為：3沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告簽。[1]張長(zhǎng)海.C語(yǔ)言程序設(shè)計(jì)[M].北京：高等教育出版社，2006語(yǔ)言課程設(shè)計(jì)案例精編.北京：清華大學(xué)出版社，2011.語(yǔ)言課程設(shè)計(jì)案例精編.北京：中國(guó)水利水電出版社，2004.[4]姜靈芝，余鍵.C語(yǔ)言課程設(shè)計(jì)案例精編.北京：清華大學(xué)出版社，2008.[5]黃明，梁旭，萬(wàn)洪莉.C語(yǔ)言課程設(shè)計(jì).北京：電子工業(yè)出版社，2006附錄(關(guān)鍵部分程序清單)返回0printf("請(qǐng)輸入與第%d條邊相連的兩條邊v1v2:",k+1);PathMatrixp.}}}沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)總結(jié)：此次課程設(shè)計(jì)中，我了解到了許多以前不太會(huì)的知識(shí)，也在對(duì)程序的不斷的調(diào)試中認(rèn)識(shí)到調(diào)試時(shí)的細(xì)心是很重要的，這些都讓我受益匪淺。譬如，getchar()的使用，用在輸入字符型數(shù)據(jù)的時(shí)候，getchar()可以將空格吸收從而避免將空格帶入數(shù)據(jù)中。在這次課程設(shè)計(jì)中，我還理解了數(shù)據(jù)結(jié)構(gòu)給成個(gè)程序帶來(lái)的簡(jiǎn)潔性以及函數(shù)的調(diào)用，數(shù)據(jù)結(jié)構(gòu)將繁瑣的程序分成幾個(gè)部分，看起來(lái)簡(jiǎn)單易懂。這些都是我在以前的學(xué)習(xí)中不理解的，讓我在這次課程設(shè)計(jì)中學(xué)