Improve it little by little Total Flow:16 18 19 flow 9+2 capacity +2=10 8 8-1=7 6+2=8 10 2 8 66 10 +1=9 8 +1 8+1 10 10 9 d 10 Ford-Fulkerson Algorithm: a initialize flow f to 0 while there exists an augmenting path p Inject more flow along p (as much as possible) return f Question 1:What is an augmenting path? 8Improve it little by little Ford-Fulkerson Algorithm: ◼ initialize flow 𝑓 to 0 ◼ while there exists an augmenting path 𝑝 ❑ Inject more flow along 𝑝 (as much as possible) ◼ return 𝑓 ◼ Question 1: What is an augmenting path? s a b c 10 d t 10 9 8 4 10 2 6 10 8 0 6 8 8 10 8 0 6 flow Total Flow: 16 capacity +2=8 +2=2 +2=10 +1 +1 -1=7 +1=3 +1=9 18 19 8