Successive shortest paths: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 30: Line 30:
# In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> from the set of nodes <math>v\in V</math> with <math>I_f(v)<0</math> to the set of nodes <math>w\in V</math> with <math>I_f(v)>0</math>.
# In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> from the set of nodes <math>v\in V</math> with <math>I_f(v)<0</math> to the set of nodes <math>w\in V</math> with <math>I_f(v)>0</math>.
# Let <math>v_0</math> be the node where <math>p</math> actually starts and <math>w_0</math> the node where <math>p</math> actually ends.
# Let <math>v_0</math> be the node where <math>p</math> actually starts and <math>w_0</math> the node where <math>p</math> actually ends.
# Let <math>\varepsilon>0</math> denote the minimum of <math>|I_f(v_0)|</math>, <math>I_f(w_0)>0</math>, and all [[Basic graph definitions
# Let <math>\varepsilon>0</math> denote the minimum of <math>|I_f(v_0)|</math>, <math>I_f(w_0)>0</math>, and the [[Basic graph definitions#Residual network|residual capacities]] of all arcs on <math>p</math>.

Revision as of 10:50, 23 October 2014

Abstract view

Definition:

  1. For a node [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ \Delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v) }[/math].
  2. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ I_f(v):=\Delta f(v)-b(v) }[/math].
  3. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is underestimating if [math]\displaystyle{ 0\leq \Delta f(v)\leq b(v) }[/math] or [math]\displaystyle{ 0\geq\Delta f(v)\geq b(v) }[/math].
  4. The total imbalance of [math]\displaystyle{ f }[/math] is the defined as [math]\displaystyle{ \sum_{v\in V}|I_f(v)| }[/math].

Invariant:

  1. The capacity constraints are fulfilled, that is, [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
  2. There is no negative cycle in the residual network of [math]\displaystyle{ f }[/math].
  3. The imbalance of every node is underestimating.

Variant: The total imbalance strictly decreases.

Break condition: The imbalances of all nodes are zero.

Induction basis

Abstract view: Start with the zero flow.

Proof: Obvious.

Induction step

  1. In the residual network of [math]\displaystyle{ f }[/math], find a shortest path [math]\displaystyle{ p }[/math] from the set of nodes [math]\displaystyle{ v\in V }[/math] with [math]\displaystyle{ I_f(v)\lt 0 }[/math] to the set of nodes [math]\displaystyle{ w\in V }[/math] with [math]\displaystyle{ I_f(v)\gt 0 }[/math].
  2. Let [math]\displaystyle{ v_0 }[/math] be the node where [math]\displaystyle{ p }[/math] actually starts and [math]\displaystyle{ w_0 }[/math] the node where [math]\displaystyle{ p }[/math] actually ends.
  3. Let [math]\displaystyle{ \varepsilon\gt 0 }[/math] denote the minimum of [math]\displaystyle{ |I_f(v_0)| }[/math], [math]\displaystyle{ I_f(w_0)\gt 0 }[/math], and the residual capacities of all arcs on [math]\displaystyle{ p }[/math].