華北電力大學(xué)電子與通信工程系-資料下載頁
2025-07-18 14:13本頁面
【正文】 Vi， 為 ? 2. 從 T中選取一個其距離值為最小的頂點(diǎn) W，加入 S 3. 對 T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn) W作中間頂點(diǎn)，從 V0到 Vi的距離值比不加 W的路徑要短，則修改此距離值 4. 重復(fù)上述步驟，直到 S中包含所有頂點(diǎn)，即 S=V為止 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 13 V0,V1 8 V0,V2 ? 30 V0,V4 ? 32 V0,V6 V2:8 V0,V2 13 V0,V1 13 V0,V2,V3 30 V0,V4 ? 32 V0,V6 V1:13 V0,V1 13 V0,V2,V3 30 V0,V4 22 V0,V1,V5 20 V0,V1,V6 V3:13 V0,V2,V3 19 V0,V2,V3,V4 22 V0,V1,V5 20 V0,V1,V6 V4:19 V0,V2,V3,V4 終點(diǎn) 從 V0到各終點(diǎn)的最短路徑及其長度 V1 V2 V3 V4 V5 V6 Vj 21 V0,V2,V3,V4,V5 20 V0,V1,V6 V6:20 V0, V1,V6 5 1 6 4 3 2 0 8 5 6 2 30 13 7 17 32 9 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 算法實(shí)現(xiàn) ① 圖用帶權(quán)鄰接矩陣存儲 ad[][] ② 數(shù)組 dist[]存放當(dāng)前找到的從源點(diǎn) V0到每個終點(diǎn)的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值 ③ 數(shù)組 pre[]表示從 V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號；若從 V0到某終點(diǎn)無路徑，則用 0作為其前一頂點(diǎn)的序號 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 算法描述 T(n)=O(n178。) 6 2 7 5 4 3 1 8 5 6 2 30 13 7 17 32 9 ?????????????????????????????????????????????????????????017020605079032308131[ ] [ ]addist 0 1 2 3 4 5 6 0 13 8 ? 30 ? 32 pre 0 1 2 3 4 5 6 0 1 1 0 1 0 1 (1) k=1 1 13 3 1 22 20 2 2 19 4 1 2151 1 1 長度 最短路徑 13 V1,V2 8 V1,V3 13 V1,V3,V4 19 V1,V3,V4,V5 21 V1,V3,V4,V5,V6 20 V1,V2,V7 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 每一對頂點(diǎn)之間的最短路徑 方法一：每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法 n次 —— T(n)=O(n179。) 方法二：弗洛伊德 (Floyd)算法 算法思想：逐個頂點(diǎn)試探法 求最短路徑步驟 ① 初始時設(shè)置一個 n階方陣，令其對角線元素為 0，若存在弧 Vi,Vj， 則對應(yīng)元素為權(quán)值；否則為 ? ② 逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值 ③ 所有頂點(diǎn)試探完畢，算法結(jié)束 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 例 A C B 2 6 4 3 11 0 4 11 6 0 2 3 ? 0 初始： 路徑： AB AC BA BC CA 0 4 6 6 0 2 3 7 0 加入 V2： 路徑： AB ABC BA BC CA CAB 0 4 11 6 0 2 3 7 0 加入 V1： 路徑： AB AC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入 V3： 路徑： AB ABC BCA BC CA CAB 軟 件 技 術(shù) 基 礎(chǔ) 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 算法實(shí)現(xiàn) 圖用鄰接矩陣存儲 length[][]存放最短路徑長度 path[i][j]是從 Vi到 Vj的最短路徑上 Vj前一頂點(diǎn)序號 例 1 3 2 2 6 4 3 11 初始： 0 4 11 6 0 2 3 ? 0 length= 0 1 1 2 0 2 3 0 0 path= 加入 V1： 0 4 11 6 0 2 3 7 0 length= 0 1 1 2 0 2 3 1 0 path= 加入 V2： 0 4 6 6 0 2 3 7 0 length= 0 1 2 2 0 2 3 1 0 path= 加入 V3： 0 4 6 5 0 2 3 7 0 length= 0 1 2 3 0 2 3 1 0 path= ? 算法分析： T(n)=O(n179。)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1