Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What exactly is augmenting path?

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?

like image 719
Jackson Tale Avatar asked May 01 '12 11:05

Jackson Tale


People also ask

What is an augmenting path in flow graph?

An augmenting path is a simple path from source to sink which do not include any cycles and that pass only through positive weighted edges. A residual network graph indicates how much more flow is allowed in each edge in the network graph. If there are no augmenting paths possible from to , then the flow is maximum.

What is an augmenting path in G FG F?

An augmenting path goes from the source s to the sink t in the residual graph Gf. A blocking flow is a flow, found on an augmenting path, that contains an edge whose capacity c(i, j) is equal to the flow f(i, j).

What is augmenting path in Ford-Fulkerson?

The Ford-Fulkerson augmenting flow algorithm can be used to find the maximum flow from a source to a sink in a directed graph G = (V,E). Each arc (i,j) ∈ E has a capacity of uij. We find paths from the source to the sink along which the flow can be increased.


1 Answers

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.

like image 83
Ivaylo Strandjev Avatar answered Sep 21 '22 10:09

Ivaylo Strandjev