Ford-Fulkerson标号算法示例 流网络 0.初始化：Ha∈E,令f(a)=0 (s,+,16 0/12 1.l(x)=o;L={x};S=0 (S,∞) 0/16 0/20 1(v1)=16-0=16 070 l(v2)=13-0=13 09 S 0/13 0/4 L={s,1,v2}-{S={1,v2} V2 S=S+{s}={S} 0/14 V4 (s,+,13)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 0.初始化: ∀𝑎 ∈ 𝐸,令𝑓 𝑎 = 0 1. 𝑙 𝑥 = ∞; 𝐿 = 𝑥 ; 𝑆 = ∅ 𝑙 𝑣1 = 16 − 0 = 16 𝑙 𝑣2 = 13 − 0 = 13 (𝑠, +, 16) (𝑠, +, 13) (𝑠, , ∞) 𝐿 = 𝑠, 𝑣1, 𝑣2 − s = 𝑣1, 𝑣2 𝑆 = 𝑆 + 𝑠 = {𝑠}
Ford-Fulkerson标号算法示例 流网络 L={v1,v2} (s,+,16 S={s} 0/12 (S,0∞) 0/16 0/20 00 S l(v3)=min(13,0)=0,不标记 019 l(v4)=min(13,14-0)=13,标记 0/13 0/4 L={1v2}+{v4}-{v2}={v1v4} V2 0/14 V4 S=S+{v2}={s,v2} (s,+,13) (v2,+,13)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 𝑙 𝑣3 = min(13,0) = 0 ,不标记 𝑙 𝑣4 = min(13,14 − 0) =13 ,标记 (𝑠, +, 16) (𝑠, +, 13) (𝑠, , ∞) 𝐿 = 𝑣1, 𝑣2 𝑆 = {𝑠} (𝑣2, +, 13) 𝐿 = 𝑣1, 𝑣2 + {𝑣4} − 𝑣2 = 𝑣1, 𝑣4 𝑆 = 𝑆 + 𝑣2 = {𝑠, 𝑣2}
Ford-Fulkerson标号算法示例 流网络 L={v1,v4} (S,+,16 (4,+,7) S={S,v2} 0/12. /16 V3 (S,0∞) 0/20 (v4,+,4) 00 S l(v3)=min(13,7-0)=7,标记 l(t)=min(13,4-0)=4,标记 0/13 0/4 L={v1,v4}+{v3,t}-{v4}={v1,v3,t} V2 0/14 S=S+{v4}={S,v2,v4} (s,+,13) (v2,+,13)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 𝑙 𝑣3 = min(13,7 − 0) =7 , 标记 𝑙 𝑡 = min(13,4 − 0) = 4 ,标记 (𝑠, +, 16) (𝑠, +, 13) (𝑠, , ∞) 𝐿 = 𝑣1, 𝑣4 𝑆 = {𝑠, 𝑣2} (𝑣2, +, 13) 𝐿 = 𝑣1, 𝑣4 + {𝑣3,𝑡} − 𝑣4 = 𝑣1, 𝑣3,𝑡 𝑆 = 𝑆 + 𝑣4 = {𝑠, 𝑣2, 𝑣4} (𝑣4, +, 7) (𝑣4, +, 4)
Ford-Fulkerson标号算法示例 流网络 L={v1,v4} (S,+,16 (4,+,7) S={S,v2} 012. 116 V3 (S,0∞) 0/20 (U4,+,4) 00 S l(v3)=min(13,7-0)=7,标记 t l(t)=min(13,4-0)=4,标记 4/13 414 L={v1,v4}+{v3,t}-{v4}={v1,v3,t} V2 4/14 S=S+{v4}={x,2,v4} (s,+,13) (v2,+,13)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 𝑙 𝑣3 = min(13,7 − 0) =7 , 标记 𝑙 𝑡 = min(13,4 − 0) = 4 ,标记 (𝑠, +, 16) (𝑠, , ∞) 𝐿 = 𝑣1, 𝑣4 𝑆 = {𝑠, 𝑣2} (𝑣2, +, 13) 𝐿 = 𝑣1, 𝑣4 + {𝑣3,𝑡} − 𝑣4 = 𝑣1, 𝑣3,𝑡 𝑆 = 𝑆 + 𝑣4 = {𝑥, 𝑣2, 𝑣4} (𝑣4, +, 7) (𝑣4, +, 4) 4/14 (𝑠, +, 13)
Ford-Fulkerson标号算法示例 流网络 1f升=4 0/L12 1.l(S=o;L={x};S=0 (S,∞) 0/16 0/20 00 8 S 4/13 4/4 4/14
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 4/14 1. 𝑙 𝑠 = ∞; 𝐿 = 𝑥 ; 𝑆 = ∅ 𝑓 =4