Edmonds–Karp algorithm: Difference between revisions

Revision as of 23:08, 24 December 2005

Revision as of 03:38, 5 January 2006

Line 10:

[[Image:ek-flow_comp1.png|right]]

The length of the augmenting paths found never decreases. For a new path to open, flow must have been sent in the opposite direction along at least one of its egdesedges. Assume that flow was sent along the path <math>s \dots w u v x \dots t</math> (green), such that there opened a path <math>s \dots y v u z \dots t</math> (blue) which was shorter, and that only one edge on this path was closed previously. Since we always choose the shortest path, we know that <math>|s \dots w u v| <= |s \dots y v|</math>, which means that <math>|s \dots w u| <= |s \dots y v| - 1</math>, as the length of <math>uv</math> is 1. Likewise we know that <math>|u v x \dots t| <= |u z \dots t|</math>, which means that <math>|v x \dots t| <= |u z \dots t| - 1</math>. From this we conclude that <math>|s \dots w u v x \dots t| <= |s \dots y v u z \dots t| - 2</math>, which contradicts the assumption that the second path was shorter. The argument can be extended to cases where multiple edges in the second path are opened when flow is sent on the first.

The number of times each edge is saturated is <math>O(V)</math>. We know that if <math>uv</math> is saturated when sending flow along a path, flow must be sent in the opposite direction, on <math>vu</math> on a second path, before flow can be sent on <math>uv</math> again, on a third path. The first path must be shorter than the second, which again must be shorter than the third. For each edge, the series of augmenting paths which saturise<!-- what word is that? --> it have strictly increasing length. Since paths do not have cycles, their length is <math>O(V)</math>. Hence the number of saturising<!-- what word is that? --> sends on an edge is <math>O(V)</math>.

Each time a path is found, at least one of the <math>E</math> edges is saturated. Since each edge saturises<!-- what word is that? --> <math>O(V)</math> times, the maximum flow is found in <math>O(VE)</math> rounds. As the cost of a breadth-first-search is <math>O(V+E)</math>, the total running time is <math>O(VE^2)</math> (if <math>E<V</math> we can remove the unused nodes in O(V) first).