軟件基礎(chǔ)課程設(shè)計--從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑(編輯修改稿)
2025-07-10 17:24 本頁面
【文章內(nèi)容簡介】 4 一、 應(yīng)用 迪科斯徹 （ Dijkstra）算法計算最短路徑 假設(shè)西安、北京、沈陽、武漢 4個城市構(gòu)成小型交通網(wǎng)， 4個城市表示圖的 4個頂點(diǎn)，他們構(gòu)成了無向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。 這里路徑指兩頂點(diǎn)間的通路，路徑的長度指所有經(jīng)過的邊的總長?！白疃搪窂健钡膯栴}指當(dāng)兩個頂點(diǎn)間通路多于一條時，如何找出邊長總和為最短的那條。Dijkstra 提出按路徑長度遞增的次序求最短路徑的方法。 二、 Dijkstra 求最短路徑的基本思想 把頂點(diǎn)分成兩組，第一 組是已確定最短路徑的結(jié)點(diǎn)的集合，第二組是尚未確定最短路徑的結(jié)點(diǎn)的集合。按路徑長度遞增的次序逐個把第二組的頂點(diǎn)放到第一組中。設(shè)求從 v0到其它各頂點(diǎn)間的最短路徑 ,則在任意時刻，從 v0 到第一組各頂點(diǎn)間的最短路徑都不大于從 v0到第二組各頂點(diǎn)間的最短路徑。 三、 Dijkstra 求最短路徑的步驟 設(shè)圖以鄰接矩陣 arcs 存儲，矩陣中各元素的值為各邊的權(quán)值。 頂點(diǎn)到自身的權(quán)值 用 0 表示 ， 頂點(diǎn)間無邊時其對應(yīng)權(quán)值用 1表示。從頂點(diǎn) v0到其它各頂點(diǎn)間的最短路徑的具體步驟如下： （ 1）初始化：第一組（集合 s）只含 頂點(diǎn) v0,第二組（集合 vs）含有圖中其余頂點(diǎn)。設(shè)一 D向量，其下標(biāo)是各頂點(diǎn)，元素值是頂點(diǎn) v0到各頂點(diǎn)的邊的權(quán)值。若 v0 到某頂點(diǎn)無邊， D 向量中的對應(yīng)值為 1。 （ 2）選 D 中最小的權(quán)值，將其頂點(diǎn)（ j）加入 s集合。 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次。由此求得 v0 到圖上其余各頂點(diǎn)得最短路徑。 正文 — 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 5 四、 程序說明 為了編程方便，以 V0代表北京 ， V1 代表西安 ， V2 代表沈陽 ， V3 代表武漢 。 首先輸入兩點(diǎn)之間的距離，即為矩陣中各元素的值 。頂點(diǎn)到自身的權(quán)值用 0 表示，頂點(diǎn)間無邊時其對應(yīng)權(quán)值用 1表示 。 五、 功能實(shí)現(xiàn) 1）測試 1： 假設(shè) ： V0～ V1之間距離是 5； V0～ V2之間距離是 8； V0～ V3之間距離是 9； V1～ V2之間距離是 2； V1～ V3之間距離是 3； V2～ V3之間距離是 1。 如圖： 圖的鄰接矩陣如下： ?????????????0139102832059850.arcsG 運(yùn)行程序： ① 運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。 9 V3 V2 V1 V0 3 1 2 8 5 正文 — 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 6 ② 、 輸入數(shù)據(jù) 之后，程序給出所求的 鄰接矩陣、最短路徑、 最短 距離 。 正文 — 從某個源點(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。 如圖： 圖的鄰接矩陣如下： 2 V2 V3 V1 V0 2 5 7 正文 — 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 8 ?????????????????0257202152017110.a r c sG 運(yùn)行程序： ① 運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。 ② 、 輸入數(shù)據(jù) 之后，程序給出 所求的鄰接矩陣、最短路徑、最短距離。 正文 — 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 9 結(jié)果分析： 根據(jù)程序的運(yùn)行結(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 之間 不連通 。 正文 — 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 10 如圖： 圖的鄰接矩陣如下： ?????????????????0
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1