Edmonds–Karp algorithm: Difference between revisions

Revision as of 06:17, 11 April 2006

Revision as of 17:20, 9 May 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 edges. 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| <=\leq |s \dots y v|</math>, which means that <math>|s \dots w u| <=\leq |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| <=\leq |u z \dots t|</math>, which means that <math>|v x \dots t| <=\leq |u z \dots t| - 1</math>. From this we conclude that <math>|s \dots w u v x \dots t| <=\leq |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 saturated it have strictly increasing length. Since paths do not have cycles, their length is <math>O(V)</math>. Hence the number of saturating sends on an edge is <math>O(V)</math>.