Explanation of path augmenting when there are backward arcs. Labeling algorithm & maximum flow minimum cut theorem Discuss augmenting path algorithm in more detail.
1. How do we know if there are any more augmenting paths?
2. Will the algorithm terminate in an infinite number of steps?
3. Will the algorithm terminate at opt.?
In general the algorithm fans out from s labeling nodes - we can label a node if we can reach that node in the residual network (that is there is a path with rij > 0 for all arcs in the path). When we label the sink, stop and augment flow. If we can't label the sink stop.