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