What exactly is augmenting path?

Question

When talking about computing network flows, the Algorithm Design Manual says:

Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the flow. It can be shown that the flow through a network is optimal if and only if it contains no augmenting path.

I don't understand what is augmenting paths. I have googled, and found:

• Augmenting Path in Wolfram

• Flow network in Wiki

but they all reference to the quote above.

Can anyone please really clearly explain what is an augmenting path?

Renny

Answer 1

An augmenting path is a simple path - a path that does not contain cycles - through the graph using only edges with positive capacity from the source to the sink.

So the statement above is somehow obvious - if you can not find a path from the source to the sink that only uses positive capacity edges, then the flow can not be increased.

By the way the proof of that statement is not that easy.

Holmium

Answer 2

Augmenting means increase-make larger. In a given flow network G=(V,E) and a flow f an augmenting path p is a simple path from source s to sink t in the residual network Gf. By the definition of residual network, we may increase the flow on an edge (u,v) of an augmenting path by up to a capacity Cf(u,v) without violating constraint, on whichever of (u,v) and (v,u) is in the original flow network G. Also the maximum amount by which we can increase the flow on each edge in an augmented path p is called the residual capacity of p. The proof can be found in the introduction to algorithms by thomas h. cormen etc...

Trophozoite

Answer 3

And how do you find out the augmenting path from source to sink? Using modified version of BFS. You do BFS from source till you reach sink and you traverse an edge only if it has residual capacity (i.e. for that edge, its max capacity - current flow > 0). And for this path from source to sink, you maintain minimum residual capacity, which is the maximum flow you can pass through that path. High level code snippet to get the idea:

bool maxFlowAchieved = false;
int maxFlow = 0;  // keeps track of what is the max flow in the network
while(!maxFlowAchieved)
{
    //BFS returns collection of Edges in the traversal order from source to sink
    std::vector<Edge*> path = BFS(source, sink); 
    maxFlowAchieved = path.size() == 0;  // all paths exhausted
    if(maxFlowAchieved)
        break;
    // traverse each edge in the path and find minimum residual capacity
    // edge->residual = edge->maxCapacity - edge->currentflow
    int allowedFlow = GetMinResidualOnPath(path);
    // Now add additional flow to each edge in the path. 
    // i.e. for each edge in path, edge->currentflow += allowedFlow
    // clearly, edge->currentflow + allowedFlow <= edge->maxCapacity
    SaturatePath(path, allowedFlow);
    maxFlow += allowedFlow;
}

return maxFlow;

Histrionism

Answer 4

A process of finding flows from source to sink iteratively. For e.g., in the case of Ford-Fulkerson algorithm, initially all the flows on all the edges are Zero. On iteration we take the values for every path/edge leading us to find flows called augmenting paths.

Pepys

An augmenting path is a path (as hinted by its name) and not a process. The process of optimizing the flow finding augmenting paths is a flow algorithm. – Holmium