軟件基礎(chǔ)課程設(shè)計--從某個源點到其余各頂點的最短路徑-文庫吧資料
2025-06-12 17:24本頁面
【正文】 求 出 從某個源點到其余各頂點的最短路徑。 七、 課程設(shè)計總結(jié) 通過 課程設(shè)計 ，我 學(xué)會 了如何 建立圖的鄰接表，理解 了 圖的基本概念。 動態(tài)鏈接庫： dll 不必被包含在最終的 EXE 中， EXE 文件執(zhí)行時可以動態(tài)地引用和卸載 DLL文件。 然后把 剛才項目 生 成 的 .lib、 .dll 文件拷貝到 該 工程的 debug 目錄下 。 正文 — 從某個源點到其余各頂點的最短路徑 14 靜態(tài)連接 DLL代碼： ②、 新建 一個空的工程， 項目名稱“ sushu” 。 動態(tài)連接 DLL調(diào)用 代碼： 正文 — 從某個源點到其余各頂點的最短路徑 13 ③ 、 運行結(jié)果： 2）、靜態(tài)連接 ①、 新建項目 “ Win32 DynamicLink Library” 項目名稱“ sushu” ,然后新建一個 “ ” 文件，輸入第一張圖片代碼。 然后新建一個“ ”文件 ，文件代碼如下。 正文 — 從某個源點到其余各頂點的最短路徑 12 1）、動態(tài)連接 ①、 新建項目 “ Win32 DynamicLink Library” 項目名稱“ sushu” ,然后新建一個 “ ” 文件，輸入以下代碼。 B：調(diào)用動態(tài)鏈接庫生成的 EXE 執(zhí)行文件。嘗試把自己編寫的程序?qū)懗蓜討B(tài)鏈接庫和靜態(tài)鏈接庫形式 ，并比較以下三種EXE文件的大小。 ② 、 輸入數(shù)據(jù) 之后，程序給出所求的鄰接矩陣、最短路徑、最短距離。 正文 — 從某個源點到其余各頂點的最短路徑 9 結(jié)果分析： 根據(jù)程序的運行結(jié)果，我們可知： ① 、 V0到 V0的最短路徑的距離為： 0 路徑： V0 V0 ② 、 V0到 V1的最短路徑的距離為： 11 路徑： V0 V3 V2 V1 ③ 、 V0到 V2的最短路徑的距離為： 9 路徑： V0 V3 V2 ④ 、 V0到 V3的最短路徑的距離為： 7 路徑： V0 V3 3）測試 3： 假設(shè)： V0～ V1 之間 不連通 ； V0～ V2之間 距離是 3； V0～ V3之間距離是 9； V1～ V2之間距離是 2； V1～ V3之間距離是 3； V2～ V3 之間 不連通 。 如圖： 圖的鄰接矩陣如下： 2 V2 V3 V1 V0 2 5 7 正文 — 從某個源點到其余各頂點的最短路徑 8 ?????????????????0257202152017110.a r c sG 運行程序： ① 運行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。 9 V3 V2 V1 V0 3 1 2 8 5 正文 — 從某個源點到其余各頂點的最短路徑 6 ② 、 輸入數(shù)據(jù) 之后，程序給出所求的 鄰接矩陣、最短路徑、 最短 距離 。 五、 功能實現(xiàn) 1）測試 1： 假設(shè) ： V0～ V1之間距離是 5； V0～ V2之間距離是 8； V0～ V3之間距離是 9； V1～ V2之間距離是 2； V1～ V3之間距離是 3； V2～ V3之間距離是 1。 首先輸入兩點之間的距離，即為矩陣中各元素的值 。由此求得 v0 到圖上其余各頂點得最短路徑。 （ 2）選 D 中最小的權(quán)值，將其頂點（ j）加入 s集合。設(shè)一 D向量，其下標(biāo)是各頂點，元素值是頂點 v0到各頂點的邊的權(quán)值。 頂點到自身的權(quán)值 用 0 表示 ， 頂點間無邊時其對應(yīng)權(quán)值用 1表示。設(shè)求從 v0到其它各頂點間的最短路徑 ,則在任意時刻，從 v0 到第一組各頂點間的最短路徑都不大于從 v0到第二組各頂點間的最短路徑。 二、 Dijkstra 求最短路徑的基本思想 把頂點分成兩組，第一 組是已確定最短路徑的結(jié)點的集合，第二組是尚未確定最短路徑的結(jié)點的集合?！白疃搪窂健钡膯栴}指當(dāng)兩個頂點間通路多于一條時，如何找出邊長總和為最短的那條。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。 16 參考文獻(xiàn) 12 七、課程設(shè)計總結(jié) 5 六、 程序設(shè)計（二） 5 五、 功能實現(xiàn) 4 四、 程序說明
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1