【正文】 要高于執(zhí)行 |V|次 Dijkstra 算法 。容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡(jiǎn)單 ；但是 時(shí)間復(fù)雜度 比較高，不適合計(jì)算大量數(shù)據(jù)。 空間復(fù)雜度為 2O(n) ，時(shí)間復(fù)雜度也 3O( )n 。 第 3 章 實(shí) 驗(yàn)結(jié)果分析與 算法 對(duì)比 輸入數(shù)據(jù) 輸入各頂點(diǎn)之間的權(quán)值如圖 所示。 圖 輸入數(shù)據(jù)鄰接矩陣截圖 其 圖可以用如 形象的表達(dá) 102343206831289531488 圖 測(cè)試圖的結(jié)構(gòu) 實(shí)驗(yàn)結(jié)果 與分析 用上述測(cè)試數(shù)據(jù)驗(yàn)證和第二章所述算法的正確性。 其實(shí)驗(yàn)結(jié)果截圖如圖 所示。 圖 實(shí)驗(yàn)結(jié)果截圖 由結(jié)果可以分析知道 4 種算法結(jié)果一致，其最小代價(jià)均為 14，路徑均為 0→ 1→ 4→ 3。 我們使用窮舉的方法將所有可能的結(jié) 果分析出來(lái)發(fā)現(xiàn) 可以從 0 到達(dá) 3 的解為{（ 0,1,2,3），（ 0,1,2,4,3）；（ 0,1,4,3）；（ 0,4,1,2,3）；（ 0,4,3） }，其代價(jià)分別為 31，36， 14， 50， 22。所以最小距離的點(diǎn)解為 0→ 1→ 4→ 3，代價(jià)為 14。即可以驗(yàn)證了上述算法針對(duì)此數(shù)據(jù)的正確性。 算法分析與對(duì)比 通過(guò)對(duì)最短路徑 問(wèn)題的算法分析于設(shè)計(jì)，可以看到各種算法設(shè)計(jì)方法有各自不同的特點(diǎn)，不同的效率。 針對(duì)此問(wèn)題，各類算法的時(shí)間復(fù)雜度、空間復(fù)雜度等比較如表 。 表 不同設(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ò)編寫代碼實(shí)現(xiàn)，發(fā)現(xiàn)計(jì)算機(jī)和人腦不一樣，它沒(méi)有那么智能，必須確切的給他指令，它才可以完成相應(yīng)功能。 通過(guò)對(duì)最短距離的四種算法進(jìn)行設(shè)計(jì)和分析、比較，對(duì)窮舉法、回溯法、貪心法、動(dòng)態(tài)規(guī)劃法有了更深的理解。 雖然通過(guò) vc 利用文件操作、類的封裝等將 最短距離問(wèn)題用相應(yīng)算法 實(shí)現(xiàn)了，同時(shí)也做了一部分小的改進(jìn)。但是均沒(méi)有從實(shí)質(zhì)上改進(jìn)，有待進(jìn)一步研究；在分析算法復(fù)雜度的問(wèn)題上，也比較吃力，很多概念比較模糊。 參考文獻(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)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過(guò)的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說(shuō)明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝　⒖s印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。 作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有 關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 涉密論文按學(xué)校規(guī)定處理。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 致 謝 時(shí)間飛逝， 大學(xué) 的學(xué)習(xí)生活很快就要過(guò)去，在這 四年 的學(xué)習(xí)生活中，收獲了很多，而這些成績(jī)的取得是和一直關(guān)心幫助我的人分不開(kāi)的。 首先非常感謝學(xué)校開(kāi) 設(shè)這個(gè)課題，為本人日后從事計(jì)算機(jī)方面的工作提供了經(jīng)驗(yàn)，奠定了基礎(chǔ)。本次畢業(yè)設(shè)計(jì)大概持續(xù)了半年，現(xiàn)在終于到結(jié)尾了。本次畢業(yè)設(shè)計(jì)是對(duì)我大學(xué)四年學(xué)習(xí)下來(lái)最好的檢驗(yàn)。經(jīng)過(guò)這次畢業(yè)設(shè)計(jì)，我的能力有了很大的提高，比如操作能力、分析問(wèn)題的能力、合作精神、嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)等方方面面都有很大的進(jìn)步。這期間凝聚了很多人的心血，在此我表示由衷的感謝。沒(méi)有他們的幫助，我將無(wú)法順利完成這次設(shè)計(jì)。 首先，我要特別感謝我的知道郭謙功老師對(duì)我的悉心指導(dǎo)，在我的論文書寫及設(shè)計(jì)過(guò)程中給了我大量的幫助和指導(dǎo)，為我理清了設(shè)計(jì)思路和操作方法，并對(duì)我所 做的課題提出了有效的改進(jìn)方案。郭謙功老師淵博的知識(shí)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)和誨人不倦的態(tài)度給我留下了深刻的印象。從他身上，我學(xué)到了許多能受益終生的東西。再次對(duì)周巍老師表示衷心的感謝。 其次，我要感謝大學(xué)四年中所有的任課老師和輔導(dǎo)員在學(xué)習(xí)期間對(duì)我的嚴(yán)格要求，感謝他們對(duì)我學(xué)習(xí)上和生活上的幫助，使我了解了許多專業(yè)知識(shí)和為人的道理，能夠在今后的生活道路上有繼續(xù)奮斗的力量。 另外，我還要感謝大學(xué)四年和我一起走過(guò)的同學(xué)朋友對(duì)我的關(guān)心與支持，與他們一起學(xué)習(xí)、生活，讓我在大學(xué)期間生活的很充實(shí)，給我留下了很多難忘的回憶。 最后，我要感謝 我的父母對(duì)我的關(guān)系和理解，如果沒(méi)有他們?cè)谖业膶W(xué)習(xí)生涯中的無(wú)私奉獻(xiàn)和默默支持，我將無(wú)法順利完成今天的學(xué)業(yè)。 致 謝 四年的大學(xué)生活就快走入尾聲，我們的校園生活就要?jiǎng)澤暇涮?hào)，心中是無(wú)盡的難舍與眷戀。從這里走出，對(duì)我的人生來(lái)說(shuō)，將是踏上一個(gè)新的征程，要把所學(xué)的知識(shí)應(yīng)用到實(shí)際工作中去。 回首四年，取得了些許成績(jī)，生活中有快樂(lè)也有艱辛。感謝老師四年來(lái)對(duì)我孜孜不倦的教誨，對(duì)我成長(zhǎng)的關(guān)心和愛(ài)護(hù)。 學(xué)友情深，情同兄妹。四年的風(fēng)風(fēng)雨雨，我們一同走過(guò)，充滿著關(guān)愛(ài)，給我留下了值得珍藏的最美好的記憶。 在我的十幾年求學(xué)歷程里 ，離不開(kāi)父母的鼓勵(lì)和支持，是他們辛勤的勞作，無(wú)私的付出，為我創(chuàng)造良好的學(xué)習(xí)條件，我才能順利完成完成學(xué)業(yè)，感激他們一直以來(lái)對(duì)我的撫養(yǎng)與培育。 最后，我要特別感謝 我的導(dǎo)師劉望蜀 老師、 和研究生助教吳子儀 老師。是他們?cè)谖耶厴I(yè)的最后關(guān)頭給了我們巨大的幫助與鼓勵(lì)， 給了我很多解決問(wèn)題的思路， 在此表示衷心的感激。老師們認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我收益匪淺。他無(wú)論在理論上還是在實(shí)踐中，都給與我很大的幫助，使我得到不少的提高這對(duì)于我以后的工作和學(xué)習(xí)都有一種巨大的幫助，感謝 他 耐心的輔導(dǎo)。在論文的撰寫過(guò) 程中 老師們 給予我很大的幫助，幫助解決了不少的難點(diǎn)，使得論文能夠及時(shí)完成，這里一并表示真誠(chéng)的感 謝。