**end;**
Example
1 2
s t
3 4
LIST Pred
s 1 2 3 4 t
1 2
s t
3 4
LIST Pred
s 1 2 3 4 t
1 2
s t
3 4
LIST Pred
s s 1 2 3 4 t
1, 3 0 s 0 s 0 0
2, 3 (Note 2 tries to label only 3) 1
3 3
4 4
The algorithm labels *t*, augment flow
= min {2, 3, 5} = 2
1 2
s t
3 4
LIST Pred
s 1 2 3 4 t
1 2
s t
3 4
Can't label anything but *s*.
Original arcs
1 2
s t
3 4
**Correctness of the algorithm**
When it stops how do we know we have an optimal solution?
When we stop we can't label the sink.
Let *S* = set of labeled nodes
= set of unlabeled nodes
*s* *S*
*t *
Since no node in can be labeled by a node in *S *this implies
r_{ij} = 0 for all (i, j) (*S*, )
Since
what do we know about *x*_{ij}* *and *x*_{ji}?
Plug into equation 6.3
Current flow = capacity of cut [s, ]
By Property 6.1 this implies that *x* is a maximum flow and [s, ] is a minimum cut.
This establishes the algorithm correctness and the max-flow min-cut theorem.
**Share with your friends:** |