網(wǎng)絡(luò)流算法專題ppt課件(編輯修改稿)
2025-06-08 13:11 本頁面
【文章內(nèi)容簡介】 st[i]。那么迭代算法描述如下：（為了便于描述，令 n = |V’| ， S的編號為 0， T的編號為 n+1） ? step 1. 令 Short[i] ? +∞ （ 1≤i≤n+1 ）， Short[0] ? 0。 ? step 2. 遍歷每一條弧 Vi, Vj。若 Short[i] + i, j Short[j]，則令 Short[j] ? Short[i] + i, j，同時 Last[j] ? i。重復(fù)做 step 2直到不存在任何任何弧滿足此條件為止。 ? step 3. 算法結(jié)束。若 Short[n + 1]= +∞ ，則不存在從 S到 T的路徑；否則可以根據(jù) Last記錄的有關(guān)信息得到最短路徑。 ? 一次迭代算法的時間復(fù)雜度為 O(kn2)，其中 k是一個不大于 n的變量。在費用流的求解過程中， k大部分情況下都遠小于 n。 procedure costflow。 {求最小費用最大流 } var i, j, x, delta : integer。 best, last : tline。 {best：最短路長度； last：可改進路中的前趨頂點 } more : boolean。 begin repeat fillword(best, sizeof(best) shr 1, maxint)。 fillchar(last, sizeof(last), 0)。 last[1] := maxint。 best[1] := 0。 {賦初值 } repeat more := false。 for i := 1 to n do if best[i] maxint then for j := 1 to n do begin if (flow[i, j] limit[i, j]) and (best[i] + cost[i, j] best[j]) then begin best[j] := best[i] + cost[i, j]。 last[j] := i。 more := true。 end。 if (flow[j, i] 0) and (best[i] cost[j, i] best[j]) then begin best[j] := best[i] cost[j, i]。 last[j] := i。 more := true。 end。 end。 until not more。 {找最優(yōu)可改進路 } if best[n] = maxint then break。 delta := maxint。 i := n。 repeat j := i。 i := abs(last[j])。 if last[j] 0 then x := limit[i, j] flow[i, j] else x := flow[j, i]。 if x delta then delta := x。 until i = 1。 {求改進量 } i := n。 repeat j := i。 i := abs(last[j])。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。 until i = 1。 until false。 {根據(jù)改進量放大流 } end。 思維發(fā)散與探索 ? 可改進路費用：“遞增！遞增？” 設(shè) f從零流到最大流共被改進了 k次，每 i次選擇的可改進路的費用為 pi，那么會不會有p1≤p 2≤p 3≤……≤p k呢？ ? 迭代法：“小心死循環(huán)！嘿嘿 ……” 迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構(gòu)造的帶權(quán)有向圖 B中會存在負回路嗎？ ? 費用：“你在乎我是負數(shù)嗎？” ? 容量：“我管的可不僅是弧?！? 網(wǎng)絡(luò)流圖中的“容量”都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務(wù)仍然是求從 S到 T的最小費用最大流。你能解決嗎？ 有上下界的最大流 ? 上面討論的網(wǎng)絡(luò)流都只對每條弧都限定了上界（其實其下界可以看成 0），現(xiàn)在給每條弧 Vi, Vj加上一個下界限制 Aij (即必須滿足 Aij≤f ij)。 ? 弧上數(shù)字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖所示，流量是 6；但若是加入了下界的限制，它的最大流量就只有 5了。 (3,0) (3,0) (3,0) (3,0) (10,1) 原問題 3 3 3 3 0 (a) 3 2 2 3 1 (b) 增廣 怎樣找可行流 ? 一種自然的想法是去掉下界，將其轉(zhuǎn)化為只含上界的網(wǎng)絡(luò)流圖。這種美好的愿望是可以實現(xiàn)的。具體方法如下： ? 設(shè)原網(wǎng)絡(luò)流圖為 G = (V, E, C, A)，構(gòu)造不含下界的網(wǎng)絡(luò)流圖 G’ = (V’, E’, C’) ： ’ = V∪{S’, T’} x，令 h(x)= ∑ vi,vx∈E AiX ，若 h(x)≠0 ，就添加一條弧 S’, x ，其上界為 h(x) 。 x，令 h+(x)= ∑ vx,vj∈E AXi ，若 h+(x)≠0 ，就添加一條弧 x, T’ ，其上界為 h+(x) 。 Vi, Vj∈E ，都有 Vi, Vj∈E’ ，其上界 C’ ij = Cij – Aij。 T, S∈E’ ，其上界 CTS = +∞ 。 G’ 中以 S’ 為源點、 T’ 為匯點求得最大流 f’ 。若 f’ 中從 S’發(fā)出的任意一條弧是非飽和弧，則原網(wǎng)絡(luò)流圖沒有可行流。否則可得原圖的一個可行流 f = f’ + A ，即所有的 fij = f’ ij + Aij 。 （反向弧 Vi, Vj必須滿足 fij≥A ij，而非fij≥0 ），不斷放大 f，直到求出最大流。 另外一種構(gòu)圖方法 ? C’ (u, v) = C(u, v) B(u, v) ? 設(shè) ? 如果 M(i)非負，那么設(shè)一附加源 S0，則可以令 C’ (S0, i) = M(i)。 ? 如果 M(i)非負，那么設(shè)一附加匯 T0，則可以令 C’ (S0, i) = M(i)。 ? 在這樣一個加入附加源和附加匯的流網(wǎng)絡(luò) C’ 中，如果任意 g(S0, i)或 g(i, T0)都達到滿載，那么 C’ 中的這一個可行流 g一定對應(yīng)原網(wǎng)絡(luò) G中的一個可行流 f；反之G中的任意一個可行流 f都可以對應(yīng) C’ 中的一個 g(S0, i)或 g(i, T0)都滿載的流。 ?? ?? ?? EviEiu viBiuBiM ),(),( ),(),()(思考？ ? 在一個容量有上下界的流網(wǎng)絡(luò) G中，怎樣盡快求源點 s到匯點 t的一個可行的最大流？ ? 在一個容量有上下界的流網(wǎng)絡(luò) G中，怎樣盡快求源點 s到匯點 t的一個可行的最小流？ 多源點、多匯點的最大流 ? 已知網(wǎng)絡(luò)流圖有 n個源點 S S …… 、 Sn， m個匯點
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1