Ford-Fulkerson标号算法示例 流网络 If升=11 0/L12 1.l(x)=o;L={S;S=0 V3 (S,∞) 0/16 7/20 00 019 S t 11/13 4/4 V4 11/14
S t v1 v2 v3 v4 0/12 11/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 1. 𝑙 𝑥 = ∞; 𝐿 = 𝑠 ; 𝑆 = ∅ 𝑓 = 11
Ford-Fulkerson标号算法示例 流网络 (s,+,16 012. 1.l(x)=o;L={S;S=0 V3 (S,∞) 0/16 7/20 1(v1)=16-0=16 l(v2)=13-11=2 09 S 11/13 4/4 L={x,V1,v2}-{S={1,v2} V2 V4 S=S+{s}={s} (s,+,2) 11/14
S t v1 v2 v3 v4 0/12 11/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) 1. 𝑙 𝑥 = ∞; 𝐿 = 𝑠 ; 𝑆 = ∅ 𝑙 𝑣1 = 16 − 0 = 16 𝑙 𝑣2 = 13 − 11 = 2 𝐿 = 𝑥, 𝑣1, 𝑣2 − s = 𝑣1, 𝑣2 𝑆 = 𝑆 + 𝑠 = {𝑠} (𝑠, +, 16) (𝑠, +, 2)
Ford-Fulkerson标号算法示例 流网络 L={v1,v2} (s,+,16 S={s} 0/12 N' (S,0∞) 0/16 7/20 l(v3)=min(2,0)=0,不标记 9 S l(v4)=min(2,14-11)=2,标记 11/13 4/4 L={1v2}+{v4}-{v2}={v1v4} V2 S=S+{v2}={s,v2} (S,+,2) 11/14 (v2,+,2)
S t v1 v2 v3 v4 0/12 11/14 流网络 Ford-Fulkerson标号算法示例 (𝑠, , ∞) (𝑠, +, 16) (𝑠, +, 2) 𝑙 𝑣3 = min(2,0) = 0 ,不标记 𝑙 𝑣4 = min(2,14 − 11) = 2 ,标记 𝐿 = 𝑣1, 𝑣2 𝑆 = {𝑠} 𝐿 = 𝑣1, 𝑣2 + {𝑣4} − 𝑣2 = 𝑣1, 𝑣4 𝑆 = 𝑆 + 𝑣2 = {𝑠, 𝑣2} (𝑣2, +, 2)