【正文】 在論文的撰寫(xiě)過(guò) 程中 老師們 給予我很大的幫助，幫助解決了不少的難點(diǎn)，使得論文能夠及時(shí)完成，這里一并表示真誠(chéng)的感 謝。老師們認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我收益匪淺。 最后，我要特別感謝 我的導(dǎo)師劉望蜀 老師、 和研究生助教吳子儀 老師。四年的風(fēng)風(fēng)雨雨，我們一同走過(guò)，充滿(mǎn)著關(guān)愛(ài)，給我留下了值得珍藏的最美好的記憶。感謝老師四年來(lái)對(duì)我孜孜不倦的教誨，對(duì)我成長(zhǎng)的關(guān)心和愛(ài)護(hù)。從這里走出，對(duì)我的人生來(lái)說(shuō)，將是踏上一個(gè)新的征程，要把所學(xué)的知識(shí)應(yīng)用到實(shí)際工作中去。 最后，我要感謝 我的父母對(duì)我的關(guān)系和理解，如果沒(méi)有他們?cè)谖业膶W(xué)習(xí)生涯中的無(wú)私奉獻(xiàn)和默默支持，我將無(wú)法順利完成今天的學(xué)業(yè)。 其次，我要感謝大學(xué)四年中所有的任課老師和輔導(dǎo)員在學(xué)習(xí)期間對(duì)我的嚴(yán)格要求，感謝他們對(duì)我學(xué)習(xí)上和生活上的幫助，使我了解了許多專(zhuān)業(yè)知識(shí)和為人的道理，能夠在今后的生活道路上有繼續(xù)奮斗的力量。從他身上，我學(xué)到了許多能受益終生的東西。 首先，我要特別感謝我的知道郭謙功老師對(duì)我的悉心指導(dǎo)，在我的論文書(shū)寫(xiě)及設(shè)計(jì)過(guò)程中給了我大量的幫助和指導(dǎo)，為我理清了設(shè)計(jì)思路和操作方法，并對(duì)我所 做的課題提出了有效的改進(jìn)方案。這期間凝聚了很多人的心血，在此我表示由衷的感謝。本次畢業(yè)設(shè)計(jì)是對(duì)我大學(xué)四年學(xué)習(xí)下來(lái)最好的檢驗(yàn)。 首先非常感謝學(xué)校開(kāi) 設(shè)這個(gè)課題，為本人日后從事計(jì)算機(jī)方面的工作提供了經(jīng)驗(yàn)，奠定了基礎(chǔ)。 涉密論文按學(xué)校規(guī)定處理。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書(shū) 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有 關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。 作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。 參考文獻(xiàn) [1]鄭宗漢、鄭曉明等 . 算法設(shè)計(jì)與分析 [M]. 北京；清華大學(xué)出版社， 2020年 . [2]鄭阿奇、丁有和等 .Visual C++教程 [M]. 北京； 機(jī)械工業(yè)出版社， 2020年 . [3]嚴(yán)蔚敏、吳偉明等 .數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） [M]. 北京；清華大學(xué)出版社， 2020年 . [4]曾方俊 . Floyd算法求解最短路徑的簡(jiǎn)明方法 [J]. 價(jià)值工程 , 2020年第 9期 . [5]裴志強(qiáng)、馮海濤、劉寶娟 . dijkstra最短路徑算法 [J].微處理機(jī) ,2020年 10月 . 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說(shuō)明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 雖然通過(guò) vc 利用文件操作、類(lèi)的封裝等將 最短距離問(wèn)題用相應(yīng)算法 實(shí)現(xiàn)了，同時(shí)也做了一部分小的改進(jìn)。 表 不同設(shè)計(jì)方法的比較 設(shè)計(jì)方法 時(shí)間復(fù)雜度 空間復(fù)雜度 優(yōu)點(diǎn) 缺點(diǎn) 是否最優(yōu) 窮舉法 3O( )n O(n!) 思路簡(jiǎn)單、算法設(shè) 計(jì)容易 必須知道所可能解、等待時(shí)間長(zhǎng) 是 回溯法 O()n 算法易理解，并 能獲得最優(yōu)解 需要知道解空間， 時(shí)間復(fù)雜度高 是 貪心法 2O(n) 2O(n) 速度快， 算法簡(jiǎn)單 一般不是最優(yōu)解 否 動(dòng)態(tài)規(guī)劃 3O( )n 2O(n) 可求的所有子 問(wèn)題以及原問(wèn) 題的最優(yōu)解 算法分析較難、速度較慢 是 第 4 章 總結(jié)與展望 最短距離問(wèn)題雖然看似比較簡(jiǎn)單，但是通過(guò)編寫(xiě)代碼實(shí)現(xiàn)，發(fā)現(xiàn)計(jì)算機(jī)和人腦不一樣，它沒(méi)有那么智能，必須確切的給他指令，它才可以完成相應(yīng)功能。 算法分析與對(duì)比 通過(guò)對(duì)最短路徑 問(wèn)題的算法分析于設(shè)計(jì)，可以看到各種算法設(shè)計(jì)方法有各自不同的特點(diǎn)，不同的效率。所以最小距離的點(diǎn)解為 0→ 1→ 4→ 3，代價(jià)為 14。 圖 實(shí)驗(yàn)結(jié)果截圖 由結(jié)果可以分析知道 4 種算法結(jié)果一致，其最小代價(jià)均為 14，路徑均為 0→ 1→ 4→ 3。 圖 輸入數(shù)據(jù)鄰接矩陣截圖 其 圖可以用如 形象的表達(dá) 102343206831289531488 圖 測(cè)試圖的結(jié)構(gòu) 實(shí)驗(yàn)結(jié)果 與分析 用上述測(cè)試數(shù)據(jù)驗(yàn)證和第二章所述算法的正確性。 空間復(fù)雜度為 2O(n) ，時(shí)間復(fù)雜度也 3O( )n 。此 算法 簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠密圖，效率要高于執(zhí)行 |V|次 Dijkstra 算法 。 arrPath (i,j): i 到 j 的路徑上 i 的后繼點(diǎn) 。所以，我們假設(shè) Dis(AB)為節(jié)點(diǎn) A 到節(jié)點(diǎn) B 的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn) X，我們檢查 Dis(AX) + Dis(XB) Dis(AB)是否成立，如果成立，證明從 A 到 X 再到 B 的路徑比 A 直接到 B 的路徑短，我們便設(shè)置 Dis(AB) = Dis(AX) + Dis(XB)，這樣一來(lái) ，當(dāng)我們遍歷完所有節(jié)點(diǎn) X， Dis(AB)中記錄的便是 A 到 B 的最短路徑的距離。 弗洛伊德 命名。 Floyd算法 又稱(chēng)為 弗洛伊德算法 ，插點(diǎn)法，是一種用于尋找給定的 加權(quán)圖 中頂點(diǎn)間 最短路徑 的算法。所以該算法要求：無(wú)論過(guò)程的初始狀態(tài)和初始決 策是什么，其余的決策必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。 該算法和貪心方法一樣，可將一個(gè)問(wèn)題的解決方案視為一系列決策的結(jié)果。其基本思想是將圓問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。 貪心法分析 針對(duì)本題中的最短路徑問(wèn)題， 在測(cè)試結(jié)果中貪心法也獲得了最優(yōu)解， 空間復(fù)雜度為 2O(n) ，時(shí)間復(fù)雜度也 2O(n) 。 (3) 修改從 v到集合 VS上任一頂點(diǎn) vi的當(dāng)前最短路徑長(zhǎng)度 :如果 dist[u]+c[u][j] dist[j] 則修改 dist[j]= dist[u]+c[u][j]。從源點(diǎn) v經(jīng)過(guò) S到圖上其余各點(diǎn) vi的當(dāng)前最短路徑長(zhǎng)度的初值為： dist[i]= weight [v][i], vi屬于 V。 n e w d i s t m _ p D i s t [ j ]更 新 頂 點(diǎn) 距 離 p D i s t [ j ] = N e w d i s t 更新 前 節(jié) 點(diǎn) p P r e v [ j ] = uj + +i + +YNYNYNNY圖 貪心法流程圖（最短距離） 其算法 步驟 可以簡(jiǎn)要描述 如下： (1) 用帶權(quán)的鄰接矩陣 c來(lái)表示帶權(quán)有向圖 , weight[i][j]表示弧 vi,vj上的權(quán)值。如果 dist[u]+weight[u][i]dist[i]，則需要更新dist[i]的值 。 dist[i]表示當(dāng)前從源到頂點(diǎn) i的最短特殊路徑長(zhǎng)度。 c是一個(gè)二維數(shù)組， wieght[i][j]表示邊 (i,j)的權(quán)。一旦 S包含了所有 V中頂點(diǎn)， dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。設(shè) u是 G的某一個(gè)頂點(diǎn)，把 從源到 u且中間只經(jīng)過(guò) S中頂點(diǎn)的路稱(chēng)為從源到 u的特殊路徑 ，并用數(shù)組 dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。一個(gè)頂點(diǎn)屬于集合 S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 利用貪心法實(shí)現(xiàn) Dijkstra算法。貪心方法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不是考慮各種可能的整體情況，所以貪心方法不要回溯。 （ 4）復(fù)雜度分析 針對(duì)本最短路徑問(wèn)題，時(shí)間復(fù)雜度和空間復(fù)雜度 均比窮舉法小 ，空間復(fù)雜度 為 O()n ，時(shí)間復(fù)雜度為 2O(n) 。 Price(i)大于或等于當(dāng)前存儲(chǔ)的最小代價(jià)時(shí)停止搜索，轉(zhuǎn)向右子數(shù)搜索；當(dāng) Path(i)等于無(wú)窮時(shí)，轉(zhuǎn)向右子數(shù)搜索；當(dāng) Path(i)等于終點(diǎn)， Price(i)小于存儲(chǔ)的最 小代價(jià)時(shí)，將現(xiàn)有路徑信息更為最小路徑信息，現(xiàn)有代價(jià)更新為最小代價(jià)，轉(zhuǎn)向右子數(shù)搜索 。搜索結(jié)束后，找到最短距離問(wèn)題的最優(yōu)解。根據(jù)深度優(yōu)先，逐層向下進(jìn)行，直到該解向量為不可行解，然后回溯到該結(jié)點(diǎn)的父結(jié)點(diǎn)，再次進(jìn)行搜索。 23 1 00 11 03 00 3