軟件基礎(chǔ)課程設(shè)計(jì)--從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑-wenkub.com
2025-05-31 17:24 本頁面
【正文】 } printf(\n \n)。i++) { printf( V0 到 )。 printf(\n)。i。j++) printf(%,[i][j])。 /*以鄰接矩 陣形式輸出圖 */ for(i=0。[i][j])。 printf(到 )。j。 /*p(v)記錄 v0 到 v 的最短路徑，若 p[v][w]為TRUE，則 w 是從 v0 到 v 當(dāng)前求得最短路徑上的頂點(diǎn) */ =4。 int i,j。 printf( V1 代表 西安 \n)。j++) p[w][j]=p[v][j]。amp。 } final[v]=TRUE。D[w]min)amp。 /* 初始化，表示最短距離 min 的初始值為無窮大 */ for(w=0。 } 源代碼 19 }/*for 語句結(jié)束 */ final[0]=TRUE。w。i。G,int p[][MAXVEX],float D[]) { int v,w,i,j。 /* 圖的頂點(diǎn)個(gè)數(shù) */ char vexs[MAXVEX]。 通過課程設(shè)計(jì)，我學(xué)會(huì)了 如何 編寫 DLL 函數(shù)。 靜 態(tài)連接 DLL調(diào)用代碼： 正文 — 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 15 ③、 運(yùn) 行結(jié)果： 正文 — 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 16 3）、結(jié)果分析 靜態(tài)鏈接庫： lib 中的指令被直接包含在最終生成的 EXE 文件中。再 新建一個(gè)“ ”文件，輸入 第二張圖片 代碼。 動(dòng)態(tài)連接 DLL代碼： ②、 新建 一個(gè)空的工程， 項(xiàng)目名稱“ sushu” 。 A：調(diào)用靜態(tài)鏈接庫生成的 EXE 執(zhí)行文件。 正文 — 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 10 如圖： 圖的鄰接矩陣如下： ?????????????????0139102332019310.arcsG 運(yùn)行程序： ① 運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。 正文 — 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 7 結(jié)果分析： 根據(jù)程序的運(yùn)行結(jié)果，我們可知： ① 、 V0到 V0的最短路徑的距離為： 0 路徑： V0 V0 ② 、 V0到 V1的最短路徑的距離為： 5 路徑： V0 V1 ③ 、 V0到 V2的最短路徑的距離為： 7 路徑： V0 V1 V2 ④ 、 V0到 V3的最短路徑的距離為： 8 路徑： V0 V1 V3 2）測試 2： 假設(shè)： V0～ V1 之間 不連通 ； V0～ V2 之間 不連通 ； V0～ V3之間距離是 7； V1～ V2之間距離是 2； V1～ V3之間距離是 5； V2～ V3之間距離是 2。頂點(diǎn)到自身的權(quán)值用 0 表示，頂點(diǎn)間無邊時(shí)其對應(yīng)權(quán)值用 1表示 。 s=s {j} （ 3）修改從頂點(diǎn) v0 到集合 t(t=Vs)中各頂點(diǎn)的最短路徑長度 ,如果 D[j]+arcs[j][k]D[k] 則修改 D[k]為 D[k]=D[j]+arcs[j][k] (4) 重復(fù)（ 2）、 （ 3） n1次。從頂點(diǎn) v0到其它各頂點(diǎn)間的最短路徑的具體步驟如下： （ 1）初始化：第一組（集合 s）只含 頂點(diǎn) v0,第二組（集合 vs）含有圖中其余頂點(diǎn)。按路徑長度遞增的次序逐個(gè)把第二組的頂點(diǎn)放到第一組中。 這里路徑指兩頂點(diǎn)間的通路，路徑的長度指所有經(jīng)過的邊的總長。 4 三、 Dijkstra 求最短路徑的步驟 4 一、 應(yīng)用迪科斯徹（ Dijkstra）算法計(jì)算最短路徑 3 正文 2 目錄 1 摘要 通過一個(gè)圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣，從圖的帶權(quán)鄰接矩陣 arcs(n n)開始，遞歸地進(jìn)行 n 次更新，按一個(gè)公式，構(gòu)造出矩陣 S(1)，又用同樣的 公式由 S(1)構(gòu)造出 S(2)?最后又用同樣的公式由 S(n1)構(gòu)造出矩陣 S(n)。 4 學(xué)時(shí) 調(diào)試程序，答辯。 主要 參考
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1