algorithmgraphmax-flow

Maximum Flow of Network is NOT unique


Look at image below:

enter image description here

I'm trying to find the maximum flow from S to T using ford fulkerson algorithm, But I'm getting two answers. one is 12 the other one 14.

The Answer Which returns 12:

s->a->d->t = 2
s->b->e->t = 3
s->b->g->t = 2
s->c->b->d->t =2
s->c->g->t = 3

Again another one which returns 12:

s->a->d->t =2
s->b->e->t =3
s->b->d->t =2
s->b->g->t =2
s->c->g->t =3

And The Answer which returns 14:

s->a->e->t =2
s->b->d->t =4
s->b->e->t =3
s->b->g->t =2
s->c->g->t =3

Why is it like this? Is it normal or Am I doing Something wrong?


Solution

  • The issue is that when you are searching for an augmenting flow you are allowed to:

    1. Go forward along edges where flow is less than capacity
    2. Go backwards along edges where flow is greater than 0

    So in your first example you can add more flow by tracing the path:

    s->b->d->a->e->t (add 2 flow)
    

    Note that the portion d->a is going backwards along an edge that already has flow through it.

    From wikipedia:

    Notice that it can happen that a flow from v to u is allowed in the residual network, though disallowed in the original network: if f(u,v)>0 and c(v,u)=0 then c_f(v,u)=c(v,u)-f(v,u)=f(u,v)>0.

    Once you have increased the flow along all possible augmenting paths the value of the maximum flow will always be the same value. (Although note that there may be many different ways of achieving this value.)