【文章內(nèi)容簡介】 j}//更新 S (3) 修改從 v到集合 VS上任一頂點 vk的當前最短路徑長度 : 如果 dist[j]+c[j][k] dist[k] 則修改 dist[K]= dist[j]+c[j][k] //更新 dist和 prev (4) 重復操作 (2),(3)共 n1次 . 算法設(shè)計與分析 貪心算法 單源最短路徑 例 題 迭代 S vi d[ 2] d[ 3] d[ 4] d[ 5]初始 {1} 10 ? 30 100 1 { 1,2} 2 10 60 30 100 2 { 1,2 , 4} 4 10 50 30 90 3 { 1,2 , 3,4} 3 10 50 30 60 4 {1,2 , 3,4 ,5} 5 10 50 30 601) v1 ? v2: 10 2) v1 ? v3: 50 3) v1 ? v4: 30 4) v1 ? v5: 60 ? 10 ? 30 100? ? 50 ? ?? ? ? ? 10? ? 20 ? 60? ? ? ? ?算法設(shè)計與分析 貪心算法 voidDijkstra(int n, int v,Type dist[], int prev[], Type **c) { bool s[maxint]； for (int i=1。i=n。 i++){ dist[i]=c[v][i]； s[i]=false； if(dist[i]= =maxint) prev[i]=0； else prev[i]=v 。 } dist[v]=0； s[v]=true； for (int i=1。in； i++){ int temp=maxint； int u= v； for (int j = 1； j=n； j++) if ((!s[j])amp。amp。(dist[j]temp)){ u=j； temp=dist[j]； } s[u]=true； for (int j=1； j=n。j++) ； if((!s[j])＆＆ (c[u][j]maxint)){ Type newdist=dist[u)+c[u][j]。 if (newdistdist[j]){ dist[]]=newdist； prev[j]=u。 }}}} 單源最短路徑問題的 Dijkstra算法 分析 :用帶權(quán)鄰接矩陣表示有 n個頂點和 e條邊的帶權(quán)有向圖 ,主循環(huán)體需要 O(n)時間 ,循環(huán)需要執(zhí)行 n1次 ,所以完成循環(huán)需要 O(n2). 算法設(shè)計與分析 貪心算法 單源最短路徑 例 題 迭代 S vi d[ 2] d[ 3] d[ 4] d[ 5]初始 {1} 10 ? 30 100 1 { 1,2} 2 10 60 30 100 2 { 1,2 , 4} 4 10 50 30 90 3 { 1,2 , 3,4} 3 10 50 30 60 4 {1,2 , 3,4 ,5} 5 10 50 30 601) v1 ? v2: 10 2) v1 ? v3: 50 3) v1 ? v4: 30 4) v1 ? v5: 60 ? 10 ? 30 100? ? 50 ? ?? ? ? ? 10? ? 20 ? 60? ? ? ? ?算法實例 ? 求下圖中 v1到其余各結(jié)點的最短路徑 v1 v4 v2 v3 v6 v7 v5 20 30 50 40 55 25 70 50 25 10 70 50 0 20 50 30 ∞ ∞ ∞ ∞ 0 25 ∞ ∞ 70 ∞ ∞ ∞ 0 40 25 50 ∞ ∞ ∞ ∞ 0 55 ∞ ∞ ∞ ∞ ∞ ∞ 0 10 70 ∞ ∞ ∞ ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ ∞ 0 算法設(shè)計與分析 貪心算法 算法實例 迭代 選取 結(jié)點 S DIST (1) (2) (3) (4) (5) (6) (7) 置初值 1 0 20 50 30 ∞ ∞ ∞ 1 2 1,2 0 20 45 30 ∞ 90 ∞ 2 3 1,2,4 0 20 45 30 85 90 ∞ 3 4 1,2,4,3 0 20 45 30 70 90 ∞ 4 5 1,2,4,3,5 0 20 45 30 70 80 140 5 6 1,2,4,3,5,6 0 20 45 30 70 80 130 SHORTESTPATHS執(zhí)行蹤跡 算法設(shè)計與分析 貪心算法 算法設(shè)計與分析 貪心算法 最小生成樹 問題陳述 :設(shè) G(V,E)是一個無向連通帶權(quán)圖。 E中每條邊 (v, w)的權(quán)為 c[v][w],若 G的一個子圖 G’是一棵包含 G的所有頂點的樹，則稱 G’為 G的生成樹。 生成樹各邊權(quán)的總和稱為該生成樹的耗費。 在 G的所有生成樹中 ,耗費最小的生成樹稱為 G的最小生成樹 . 抽象描述 : 輸入 :任一連通生成子圖 (該子圖的邊集合 ) 可行解 :圖的生成樹 , 優(yōu)化函數(shù) :生成樹的各邊權(quán)值之和 最優(yōu)解 :使優(yōu)化函數(shù)達到最小的生成樹 . 4. 6 最小生成樹 算法設(shè)計與分析 貪心算法 最小生成樹 應用領(lǐng)域與圖模型 算法思路 : 首先置 S={1}, T= 216。 .若 S?V, 就作如下的貪心選擇： 選取滿足條件 i?S, j?VS,且 c[i][j]最小的邊 (i, j),將頂點 j添加到 S中邊 (i, j)添加到 T中 .這個過程一直進行到 S=V時為止 . T中的所有邊構(gòu)成 G的一棵最小生成樹。 void Prim(int n, Type * * c) { T= 216。 S ={1}。 while (S!= V) { (i, j) = i ? S且 j?V S的最小權(quán)邊 。 T=TU{(i,j)}。 S= S U{j}。 } } 算法描述 Prim算法 設(shè) G=(V,E)是一個連通帶權(quán)圖 , y={l, 2, …, n} 。 例 題 算法設(shè)計與分析 貪心算法 最小生成樹 問題：如何選取滿足條件 i?S, j?VS,且 c[i][j]最小的邊 (i, j), 成了算法難點問題。 解決方法： 設(shè)置兩個數(shù)組 closest和 lowcost。對于每個 j ?VS， closest[j]是 j在 S中的鄰接頂點，它與 j在 S中的其他鄰接頂點 k相比較有 c[j][closet[j]] ≤c[j][k]。lowcost[j]的值就是 c[j][closest[j]] 圖 Prim算法的執(zhí)行過程 97248811276414104801da( b )eica ＝ E X T R A C T M I N (Q )∥ Q ＝ { b , c , d , e , f , g , h , i}∥ V － Q ＝ {a }A dj [ a ] ＝ { b , h }?? [ b ] ＝ a , k e y[ b ] ＝ 4? [ h ] ＝ a , k e y[ h ] ＝ 8fg∞∞∞∞∞bh∞972488112764141001da( a )eicfg∞∞∞∞∞bh∞∞∞注：灰色部分表示集合 S 每個結(jié)點的上的數(shù)字表示 S中的結(jié)點到該結(jié)點的最小消耗，即lowcost 用圖示的邊的連接表示 closest 圖 Prim算法的執(zhí)行過程 97248811276414104 88 1701hdba( d )eic h ＝ E X T R A C T M I N (Q )∥ Q ＝ { c , d , e , f , g , i}∥ V － Q ＝ {a , b , h }A dj [ h ] ＝ { a , b , i , g }?? [ i ] ＝ h , k e y [ i ] ＝ 7? [ g ] ＝ h , k e y [ g ] ＝ 1fg97248811276414104801hdba( c )eicb ＝ E X T R A C T M I N (Q )∥ Q ＝ { c , d , e , f , g , h , i}∥ V － Q ＝ {a , b }A dj [ b ] ＝ { a , c , h }?? [ c ] ＝ b , k e y [ c ] ＝ 8k e y [ h ] 值 不 變fg∞∞∞∞∞∞∞∞8圖 Prim算法的執(zhí)行過程 9724881127641410∞4 88 1 260g1hdba( e )eic g ＝ E X T R A C T M I N (Q )∥ Q ＝ { c , d , e , f , i }∥ V － Q ＝ {a , b , h , g }A dj [ g ] ＝ { f , h , i }?? [ f ] ＝ g , key [ f ] ＝ 2? [ i ] ＝ g , key [ i ] ＝ 6f∞圖 Prim算法的執(zhí)行過程 97248811276414107104 48 1220fg1hc dba( g )c ＝ E X T R A C T M I N (Q )∥ Q ＝ { d , e , i }∥ V － Q ＝ {a , b , c , h , g , f }A dj [ c ] ＝ {b , d , f , i }?? [ d ] ＝ c , k e y[ d ] ＝ 7? [ i ] ＝ c , k e y[ i ] ＝ 2ei972488112764141014104 48 1 260ghdba( f )eicf ＝ E X T R A C T M I N (Q )∥ Q ＝ { c , d , e , i }∥ V － Q ＝ {a , b , h , g , f }A dj [ f ] ＝ {c , d , e , g }?? [ c ] ＝ f , k e y[ c ] ＝ 4? [