Ford-Fulkerson: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "[[Category:Max-Flow] Category:Algortihms == General Information == '''Algorithmic problem:'''Max-Flow Problems '''Prerequisites:''' '''Type of algorithm:''' loop '''A...")
 
Line 27: Line 27:


== Induction Step ==
== Induction Step ==
'''Abstract view:''' Find a flow-augmenting path and increase <math>f</math> along this path by the maximal value such that the flow value of each <math>a\inA</math> remains in the interval .
'''Abstract view:''' Find a flow-augmenting path and increase <math>f</math> along this path by the maximal value such that the flow value of each <math>a\in A</math> remains in the interval <math>[0...c(a)]</math>.<br>
Implementation:
'''Implementation:'''
Apply a graph traversal algorithm from  as follows:
# Apply a graph traversal algorithm from  as follows:
if ,  can be used for going forward in the direction ;
##if ,  can be used for going forward in the direction ;
if ,  can be used for going forward in the direction .
##if ,  can be used for going forward in the direction .
Terminate this graph traversal once either  is seen or all reachable nodes were seen (whatever occurs first).
#Terminate this graph traversal once either  is seen or all reachable nodes were seen (whatever occurs first).
In the latter case, the break condition of the loop applies.
#In the latter case, the break condition of the loop applies.
Otherwise,
#Otherwise,
let  denote the current path of the traversal (which is an -path in this case);
##let  denote the current path of the traversal (which is an -path in this case);
let  denote the minimum of the values  on all forward arcs of ;
##let  denote the minimum of the values  on all forward arcs of ;
let  denote the minimum of the values  on all backward arcs of .
##let  denote the minimum of the values  on all backward arcs of .
For each arc  on , increase the flow value by  if  is a forward arc on , otherwise, decrease the flow value by .
##For each arc  on , increase the flow value by  if  is a forward arc on , otherwise, decrease the flow value by .
Correctness: If the graph traversal does not hit , the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit . Then  is an -path. By definition of  and , the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes of  are relevant. Let  be such an internal node, and let  and  denote the immediate predecessor and successor of  on , respectively. Basically, there are four cases:
 
'''Correctness:''' If the graph traversal does not hit , the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit . Then  is an -path. By definition of  and , the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes of  are relevant. Let  be such an internal node, and let  and  denote the immediate predecessor and successor of  on , respectively. Basically, there are four cases:
Either  is on  as a forward arc or  is on  as a backward arc.
Either  is on  as a forward arc or  is on  as a backward arc.
Either  is on  as a forward arc or  is on  as a backward arc.
Either  is on  as a forward arc or  is on  as a backward arc.
It is easy to check preservation of the flow conservation conditions for each of these four cases.
It is easy to check preservation of the flow conservation conditions for each of these four cases.
'''Correctness:''' Obvious.
'''Correctness:''' Obvious.
== Pseudocode ==  
== Pseudocode ==  
<code>
<code>

Revision as of 16:59, 30 September 2014

[[Category:Max-Flow]

General Information

Algorithmic problem:Max-Flow Problems Prerequisites: Type of algorithm: loop

Auxiliary data: A pointer p of type "pointer to a B-tree node".

Abstract View

Invariant: Before and after each iteration:

  1. p points to some node N of the B-tree and
  2. the searched key is in the range of N.

Variant: p is redirected from the current node N to some child of the current node.

Break condition:

  1. p points to a leaf of the B-tree or (that is, inclusive-or)
  2. the searched key is in the node to which p points.

Induction Basis

Abstract view: p is initialized so as to point to the root of the B-tree.

Implementation: Obvious.

Proof: Obvious.

Induction Step

Abstract view: Find a flow-augmenting path and increase [math]\displaystyle{ f }[/math] along this path by the maximal value such that the flow value of each [math]\displaystyle{ a\in A }[/math] remains in the interval [math]\displaystyle{ [0...c(a)] }[/math].
Implementation:

  1. Apply a graph traversal algorithm from as follows:
    1. if , can be used for going forward in the direction ;
    2. if , can be used for going forward in the direction .
  2. Terminate this graph traversal once either is seen or all reachable nodes were seen (whatever occurs first).
  3. In the latter case, the break condition of the loop applies.
  4. Otherwise,
    1. let denote the current path of the traversal (which is an -path in this case);
    2. let denote the minimum of the values on all forward arcs of ;
    3. let denote the minimum of the values on all backward arcs of .
    4. For each arc on , increase the flow value by if is a forward arc on , otherwise, decrease the flow value by .

Correctness: If the graph traversal does not hit , the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit . Then is an -path. By definition of and , the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes of are relevant. Let be such an internal node, and let and denote the immediate predecessor and successor of on , respectively. Basically, there are four cases: Either is on as a forward arc or is on as a backward arc. Either is on as a forward arc or is on as a backward arc. It is easy to check preservation of the flow conservation conditions for each of these four cases. Correctness: Obvious.

Pseudocode

B-TREE-FIND(x,k)
1 i = 1
2 while i ≤ x.n and k > x.keyi 
3        i = i + 1
4 if ix.n and k == x.keyi 
5        return (x.i)
6 elseif  x.leaf
7        return NIL
8 else DISK-READ(x.ci) 
9        return B-TREE-FIND(x.ci,k)

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(\log n) }[/math] in the worst case.

Proof: Follows immediately from the fact that the height of B-tree with n nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).