Ahuja-Orlin: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 28: Line 28:
# We start with some feasible flow, for example, the zero flow.
# We start with some feasible flow, for example, the zero flow.
# For each <math>v\in V</math>, <math>d(v)</math> is initialized to be the smallest number of arcs from <math>v</math> to <math>t</math>.
# For each <math>v\in V</math>, <math>d(v)</math> is initialized to be the smallest number of arcs from <math>v</math> to <math>t</math>.
# Stack <math>S</math> is initialized so as to contain <math>s</math> and no other node.
# The current arc of each node <math>v\in V</math> is reset to be the very first out


'''Implementation:'''
'''Implementation:'''
# For all <math>a \in A</math>, set <math>f(a):=0. </math>  
# For all <math>a \in A</math>, set <math>f(a):=0. </math>  
# Run a [[Breadth-first search|BFS]] on the [[Basic graph definitions|transpose]] of <math>G</math> with start node <math>t</math> and unit arc lengths.
# Run a [[Breadth-first search|BFS]] on the [[Basic graph definitions|transpose]] of <math>G</math> with start node <math>t</math> and unit arc lengths; the resulting distances are the <math>d</math>-labels.
# The resulting distances are the <math>d</math>-labels.
# Create <math>S</math> and push <math>s</math> onto <math>S</math>.
# Reset the current arcs.


'''Proof:'''
'''Proof:'''

Revision as of 10:27, 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

Abstract view:‘‘‘

  1. We start with some feasible flow, for example, the zero flow.
  2. For each [math]\displaystyle{ v\in V }[/math], [math]\displaystyle{ d(v) }[/math] is initialized to be the smallest number of arcs from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ t }[/math].
  3. Stack [math]\displaystyle{ S }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and no other node.
  4. The current arc of each node [math]\displaystyle{ v\in V }[/math] is reset to be the very first out

Implementation:

  1. For all [math]\displaystyle{ a \in A }[/math], set [math]\displaystyle{ f(a):=0. }[/math]
  2. Run a BFS on the transpose of [math]\displaystyle{ G }[/math] with start node [math]\displaystyle{ t }[/math] and unit arc lengths; the resulting distances are the [math]\displaystyle{ d }[/math]-labels.
  3. Create [math]\displaystyle{ S }[/math] and push [math]\displaystyle{ s }[/math] onto [math]\displaystyle{ S }[/math].
  4. Reset the current arcs.

Proof: Obvious.

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.