7. Edmonds-Karp AlgorithmAlgorithm Designby Eva Tardos and Jon Kleinberg:Copyright2005 Addison Wesley:Slides by Kevin Wayne
Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne 7. Edmonds-Karp Algorithm
Edmonds-KarpAlgorithmflowcapacityG:Flowvalue=O
2 Edmonds-Karp Algorithm s t G: Flow value = 0 flow capacity
Edmonds-KarpAlgorithmflowcapacityG:XFlow value = 0residual capacityGf:
Edmonds-Karp Algorithm 3 s t G: s t Gf : X X X Flow value = 0 capacity residual capacity flow
Edmonds-Karp AlgorithmG:Flowvalue=8Gf
4 Edmonds-Karp Algorithm s t G: X X X s t Gf : Flow value = 8
G:XXXFlow value = 10Gf:6
5 s t G: s t Gf : X X X Flow value = 10