Ahuja-Orlin

General Information

Algorithmic problem: Max-Flow Problems

Type of algorithm: loop

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

1. The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
3. There is a valid distance labeling [math]\displaystyle{ d }[/math] with respect to [math]\displaystyle{ f }[/math].
4. Each node [math]\displaystyle{ v\in V\setminus\{t\} }[/math] has a current arc, which is either void or one of the outgoing arcs of [math]\displaystyle{ v }[/math].
5. There is a current flow-augmenting path with respect to [math]\displaystyle{ f }[/math]. This path starts with [math]\displaystyle{ s }[/math] and ends at an arbitrary node of [math]\displaystyle{ G }[/math]. Each arc on this path is the current arc of its tail node.

Variant: Exactly one of the following actions will take place in the current iteration:

1. An arc is appended to the current path.
2. At least one arc is saturated.
3. The distance label of some node is increased.

Break condition: [math]\displaystyle{ d(s)\geq n }[/math].

Remark

This algorithm may be seen as a "lazy" variant on Edmonds-Karp. In fact, the most expensive step there is the computation of a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. This task amounts to computing the true distance from every node to [math]\displaystyle{ t }[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.