[其它課程]數(shù)據(jù)結(jié)構(gòu)第17次課圖c-資料下載頁
2025-01-21 13:01本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)167。 求最短路徑步驟 (頂點(diǎn)歸并 )171。初使時(shí)令 S={V0},T={其余頂點(diǎn) }， T中頂點(diǎn)對(duì)應(yīng)的距離值v 若存在 V0,Vi， 為 V0,Vi弧上的權(quán)值v 若不存在 V0,Vi， 為 ?171。從 T中選取一個(gè)其 距離值為最小 的頂點(diǎn) W， 加入 S171。對(duì) T中頂點(diǎn)的距離值進(jìn)行修改： 若加進(jìn) W作中間頂點(diǎn)，從V0到 Vi的距離值比不加 W的路徑要短，則修改此距離值171。重復(fù)上述步驟，直到 S中包含所有頂點(diǎn)，即 S=V為止5164320856 2301371732951數(shù)據(jù)結(jié)構(gòu)13V0,V18V0,V2?30V0,V4?32V0,V6V2:8V0,V213V0,V113V0,V2,V330V0,V4?32V0,V6V1:13V0,V113V0,V2,V330V0,V422V0,V1,V520V0,V1,V6V3:13V0,V2,V319V0,V2,V3,V422V0,V1,V520V0,V1,V6V4:19V0,V2,V3,V4終點(diǎn) 從 V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj21V0,V2,V3,V4,V520V0,V1,V6V6:20V0, V1,V65164320856 2301371732952數(shù)據(jù)結(jié)構(gòu)v算法實(shí)現(xiàn)l 圖用帶權(quán) 鄰接矩陣 存儲(chǔ) ad[][]l 數(shù)組 dist[]存放當(dāng)前找到的從源點(diǎn) V0到每個(gè)終點(diǎn)的最短路徑長(zhǎng)度， 其初態(tài)為圖中直接路徑權(quán)值l 數(shù)組 pre[]表示從 V0到各終點(diǎn)的最短路徑上，此頂點(diǎn)的前一頂點(diǎn)的序號(hào) ；若從 V0到某終點(diǎn)無路徑，則用 0作為其前一頂點(diǎn)的序號(hào)（ 為什么不記錄每條路徑？ ）53數(shù)據(jù)結(jié)構(gòu)v算法描述6275431856 23013717329dist1 2 3 4 5 6 70 13 8 ? 30 ? 32pre1 2 3 4 5 6 70 1 1 0 1 0 1(1)k=11133122 202 21941215111長(zhǎng)度最短路徑13V1,V28V1,V313V1,V3,V419V1,V3,V4,V521V1,V3,V4,V5,V620V1,V2,V754數(shù)據(jù)結(jié)構(gòu)171。每一對(duì)頂點(diǎn)之間的最短路徑v方法一 ：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行 Dijkstra算法 n次 —— T(n)=O(n179。)v方法二 ：弗洛伊德 (Floyd)算法l算法思想：逐個(gè)頂點(diǎn)試探法l求最短路徑步驟u初始時(shí)設(shè)置一個(gè) n階方陣，令其對(duì)角線元素為 0，若存在弧 Vi,Vj， 則對(duì)應(yīng)元素為權(quán)值；否則為 ?u逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值u所有頂點(diǎn)試探完畢，算法結(jié)束55數(shù)據(jù)結(jié)構(gòu)例ACB2643 110 4 116 0 23 ? 0初始： 路徑：AB ACBA BCCA0 4 66 0 23 7 0加入 VB： 路徑：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入 VA： 路徑：AB ACBA BCCA CAB0 4 65 0 23 7 0加入 VC： 路徑：AB ABCBCA BCCA CAB56數(shù)據(jù)結(jié)構(gòu)171。算法實(shí)現(xiàn)u 圖用鄰接矩陣存儲(chǔ)u length[][]存放最短路徑長(zhǎng)度u path[i][j] 是從 Vi到 Vj的最短路徑上 Vj前一頂點(diǎn)序號(hào)l算法描述 例1322643 11初始：0 4 116 0 23 ? 0length=0 1 12 0 23 0 0path=加入 V1：0 4 116 0 23 7 0length=0 1 12 0 23 1 0path=加入 V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入 V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=算法分析 ：T(n)=O(n179。)57
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1