FordFulkerson

Graph theory : max flow in network

video

lecture

The problem

• The graph should be directed

• The graph is allowed to have cycles

  • But no self-looping

  • No bidirection, we cancel this kind of loop by inserting an intermedian node

    # Bidirection loop
       2
    A <-> B
       1
    # Three way loop
     1   1
    A->C->B
    ^-----|
       2

    Ford-Folkerson

The idea : repeatedly finds augmenting paths through the residual graph and augments the flow until no augmenting paths can be found

(You can see that this is a greedy algorithm)

1. start with an arbitrary path, use it as augmenting path
2. Find an another path in residual graph
3. try to augment the flow using the new path
4. Repeat until no new path

while there is an augmenting path:
	find an augmenting path using DFS
	for each edge u->v in the path:
		decrease capacity u->v by bottleneck
		increase capacity v->u by bottleneck
	increase maxflow by bottleneck