Ahuja-Orlin: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 16: Line 16:


'''Variant:'''
'''Variant:'''
If no arc is appended to tha path in the current iteration, the distance label of some node (the endnode of the path , in fact) is increased.
Exactly one of the following actions will take place in the current iteration:
# An arc is appended to the current path.
# At least one arc is [[Basic flow definitions|saturated]].
# The distance label of some node is increased.


'''Break condition:''' <math>d(s)\geq n</math>.
'''Break condition:''' <math>d(s)\geq n</math>.

Revision as of 10:02, 13 October 2014

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].

Induction basis

Induction step

Complexity

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.