NETWORK FLOW

FORD-FULKERSON (G, s, t)

for each edge (u,v) ∈ G.E

    (u,v).f = 0 Initialize all flow to be 0

while there exists a path p from s to t in the residual network G_f If there's any augmenting path

    c_f(p) = min{ c_f(u,v) : (u,v) is in p } Find the residual capacity on this path

    for each edge (u,v) in p For each edge in path

        if (u,v) ∈ E If there's an edge from u to v in E, which has some flow.

            (u,v).f = (u,v).f + c_f(p) Add that much flow

        else (u,v).f = (u,v).f - c_f(p)Otherwise send back that much flow

Try the Algorithm here

Graph G with flow

Residual Network

Step 1 Initialize all flow to be 0, build the residual network.

Graph G with flow

Residual Network

Step 2 Find an augmenting path S->V1->V3->V2->V4->T, smallest c_f(u,v) is 4.

Graph G with flow

Residual Network

Step 3 Augment the flow on this path by 4. All yellow edges, all add 4.

Graph G with flow

Residual Network

Step 4 Build current residual network.

Graph G with flow

Residual Network

Step 5 Find an augmenting path S->V2->V1->V3->T, smallest c_f(u,v) is 4.

Graph G with flow

Residual Network

Step 6 Augment the flow on this path by 4. All yellow edges, all add 4.

Graph G with flow

Residual Network

Step 7 Build the residual network.

Graph G with flow

Residual Network

Step 8 Find an augmenting path S->V1->V2->V3->T, smallest c_f(u,v) is 4.

Graph G with flow

Residual Network

Step 9 Augment the flow, for yellow ones add 4, blue ones minus 4.

Graph G with flow

Residual Network

Step 10 Build the residual network.

Graph G with flow

Residual Network

Step 11 Find an augmenting path S->V2->V4->V3->T, smallest c_f(u,v) is 7.

Graph G with flow

Residual Network

Step 12 Augment the flow on this path. All yellow edges, all add 7.

Graph G with flow

Residual Network

Step 13 Build the residual network.

Graph G with flow

Residual Network

Step 14 Find an augmenting path S->V1->V3->T, smallest c_f(u,v) is 4.

Graph G with flow

Residual Network

Step 15 Augment the flow on this path. All yellow edges, all add 4.

Graph G with flow

Residual Network

Step 16 Build the residual network.

Graph G with flow

Residual Network

No more augmenting path, found the maximum flow

Graph G with flow

Residual Network