Ford-Fulkerson标号算法示例 流网络 (s,+,16 0/12 1.l(x)=o;L={S;S=0 V3 (S,∞) 0/16 0/20 1(v1)=16-0=16 00 l(v2)=13-4=9 8 S 4/13 4/4 L={s,1,v2}-{S={v1,v2} S=S+{s}={s} 4/14 (s,+,9)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 4/14 1. 𝑙 𝑥 = ∞; 𝐿 = 𝑠 ; 𝑆 = ∅ 𝑙 𝑣1 = 16 − 0 = 16 𝑙 𝑣2 = 13 − 4 = 9 (𝑠, +, 16) (𝑠, +, 9) 𝐿 = 𝑠, 𝑣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(9,0)=0,不标记 l(v4)=min(9,14-4)=9,标记 4/13 414 L={1,v2}+{v4}-{v2}={1,4} V2 4/14 S=S+{v2}={s,v2} (s,+,9) (v2,+,9)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 4/14 (𝑠, +, 16) (𝑠, +, 9) 𝑙 𝑣3 = min(9,0) = 0 ,不标记 𝑙 𝑣4 = min(9,14 − 4) = 9 ,标记 𝐿 = 𝑣1, 𝑣2 𝑆 = {𝑠} 𝐿 = 𝑣1, 𝑣2 + {𝑣4} − 𝑣2 = 𝑣1, 𝑣4 𝑆 = 𝑆 + 𝑣2 = {𝑠, 𝑣2} (𝑣2, +, 9)
Ford-Fulkerson标号算法示例 流网络 L={1,v4} (s,+,16 (4,+,7) S={S,2} 0/12 /16 V3 (x,0∞) 0/20 00 l(v3)=min(9,7-0)=7,标记 019 S l(t)=min(9,4-4)=0,不标记 4/13 4/4 L={v1v4}+{v3}-{v4}={v1,v3} 4/14 S=S+{v4}={s,2,v4} (s,+,9) (v2,+,9)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 (𝑥, , ∞) 4/14 (𝑠, +, 16) (𝑠, +, 9) (𝑣2, +, 9) 𝑙 𝑣3 = min(9,7 − 0) =7 , 标记 𝑙 𝑡 = min(9,4 − 4) = 0 ,不标记 𝐿 = 𝑣1, 𝑣4 𝑆 = {𝑠, 𝑣2} 𝐿 = 𝑣1, 𝑣4 + {𝑣3} − 𝑣4 = 𝑣1, 𝑣3 𝑆 = 𝑆 + 𝑣4 = {𝑠, 𝑣2, 𝑣4} (𝑣4, +, 7)
Ford-Fulkerson标号算法示例 流网络 L={v1,3} (S,+,16 (v4,+,7) S={S,v2,v4} 0/12 V3 /16 (S,0∞) 0/20 (v3,+,7) 00 l(t)=min(7,20-4)=7,标记 0/9 S 4/13 414 L={v1,v4}+{t}-{v3}={v1,t 4/14 S=S+{v3}={s,v2,v3,4} (s,+,9) (2,+,9)
S t v1 v2 v3 v4 0/12 0/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 4/14 (𝑠, +, 16) (𝑠, +, 9) (𝑣2, +, 9) 𝑙 𝑡 = min(7,20 − 4) = 7 ,标记 𝐿 = 𝑣1, 𝑣3 𝑆 = {𝑠, 𝑣2, 𝑣4} 𝐿 = 𝑣1, 𝑣4 + {𝑡} − 𝑣3 = 𝑣1,𝑡 𝑆 = 𝑆 + 𝑣3 = {𝑠, 𝑣2, 𝑣3, 𝑣4} (𝑣4, +, 7) (𝑣3, +, 7)
Ford-Fulkerson标号算法示例 流网络 L={v1,3} (s,+,16 (4,+,7) S={S,v2,v4} 0/12 /16 V3 (S,0∞) 7/20 (v3,+,7) 00 l(t)=min(7,20-4)=7,标记 09 t 11/13 414 L={v1,v4}+{t}-{v3}={v1,t S=S+{v3}={s,v2,3,4} (s,+,9) 11/14 (2,+,9)
S t v1 v2 v3 v4 4/14 0/12 11 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) (𝑠, +, 16) (𝑠, +, 9) (𝑣2, +, 9) 𝑙 𝑡 = min(7,20 − 4) = 7 ,标记 𝐿 = 𝑣1, 𝑣3 𝑆 = {𝑠, 𝑣2, 𝑣4} 𝐿 = 𝑣1, 𝑣4 + {𝑡} − 𝑣3 = 𝑣1,𝑡 𝑆 = 𝑆 + 𝑣3 = {𝑠, 𝑣2, 𝑣3, 𝑣4} (𝑣4, +, 7) (𝑣3, +, 7)