圖的各種算法(深度、廣度等)(參考版)
2025-07-28 03:44本頁面
【正文】 ++i) P[v][w][i] =(P[v][u][i] || P[u][w][i])。 for (i=0。 w。 v。 u。 if (D[v][w] INFINITY) { // 從 v到 w有直接路徑 P[v][w][v] = P[v][w][w] = TRUE。 u。 ++w) { D[v][w] = [v][w].adj。 ++v) // 各對結(jié)點之間初始已知路徑及距離 for (w=0。 for (v=0。若 P[v][w][u]為 TRUE，則 u是從 v到 w當(dāng)前求得最 // 短路徑上的頂點。 求解右圖的 Allpair Shortest Path Sol: ?找出相鄰矩陣 W ?逐步求出 D1, D2, D3矩陣 ?Step 1:由 W 矩陣求出 D1 矩陣 ?????????????032061140321321vvvvvvWD 0v1 v2 v3 6 4 11 3 2 ??????????? D 1321321vvvvvv????????????032061140321321vvvvvvW0 0 0 4 11 6 3 ????????17312232 ?????????721323 2 7 ?Step 2:由 D1矩陣求出 D2 矩陣 ?Step 3:由 D2矩陣求出 D3矩陣 ???????????0732061140321321vvvvvv1D??????????? D 3321321vvvvvv???????????0732066403212321vvvvvvD0 0 0 3 7 6 2 ????????13231 421????????5132612 4 5 ??????????? D 2321321vvvvvv0 0 0 6 2 4 7 ????????63211131 ????????13123 3136 3 72 Floyd算法框架 : void ShortestPath_FLOYD(MGraph G, PathMatrix P[], DistancMatrix amp。 ?自 vi 至 vj 途中 不會經(jīng)過其它頂點 167。 當(dāng) k = 0時， 矩陣 D0[i, j]表示為 Adjacency Matrix (相鄰矩陣 。 //第 v行賦值于第 w行 P[w][w] = TRUE。j。 (min+[v][w].adjD[w])) { // 修改 D[w]和 P[w], w∈ VS D[w] = min + [v][w].adj。 ++w) // 更新當(dāng)前最短路徑及距離 if (!final[w] amp。 // 離 v0頂點最近的 v加入 S集 for (w=0。 min = D[w]。 w。 ++i) { // 其余 min = INFINITY。 // 初始化， v0頂點屬于 S集 66 // 開始主循環(huán)，每次求得 v0到某個 v頂點的最短路徑，并加 v到 S集 for (i=1。 } } D[v0] = 0。 // 設(shè)空路徑 if (D[v] INFINITY) { P[v][v0] = TRUE。 w。 D[v] = [v0][v].adj。 v。 bool final[MAX_VERTEX_NUM]。 // final[v]為 TRUE當(dāng)且僅當(dāng) v∈ S,即已經(jīng)求得從 v0到 v的最短路徑。D) {// 用 Dijkstra算法求有向網(wǎng) G的 v0頂點到其余頂點 v的最短路徑 P[v] // 及其帶權(quán)長度 D[v]。 Dijkstra算法的迭代過程 迭代 S u dist[1] dist[2] dist[3] dist[4] dist[5] dist[6] 初始 {0} 13 8 maxint 30 maxint 32 1 {0,2} 2 13 8 13 30 maxint 32 2 {0,2,1} 1 13 8 13 30 22 20 3 {0,2,1,3} 3 13 8 13 19 22 20 4 {0,2,1,3,4} 4 13 8 13 19 21 20 5 {0,2,1,3,4,6} 6 13 8 13 19 21 20 6 {0,2,1,3,4,6,5} 5 13 8 13 19 21 20 5 1 6 4 3 2 0 8 5 6 2 30 13 7 17 32 9 Dijkstra算法框架 : void ShortestPath_DIJ(MGraph G,int v0,PathMatrix amp。 2）修改其它各頂點的 Dist[k]值。 五、最短路徑 連通圖的深度優(yōu)先搜索遍歷 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點到頂點 k 的弧上的權(quán)值 或者 = 源點到 其它頂點 的路徑長度 + 其它頂點 到頂點 k 的 弧上的權(quán)值 設(shè)置輔助數(shù)組 Dist，其中每個分量 Dist[k] 表示 當(dāng)前所求得的從源點到其余各頂點 k 的最短路徑。 且 k++。 檢查邊集 E 中第 i 條權(quán)值最小的邊 (u,v)。 k = i = 0。 考慮問題的出發(fā)點 : 為使
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1