Augmenting Path Algorithms

In this post I will briefly describe one type of algorithm that has been used to solve the well-known max flow problem. This problem is essentially how to find the maximum flow that can be sent from a source node to a sink node in a network. Think of a graph connected with nodes and arcs each having a certain capacity or limit of flow that it can hold. This could be a very literal thing such as network of pipes or internet cables, but other stranger uses for network flow problems do exist such as the baseball elimination problem I talked about before.

Residual Capacities

The augmenting path algorithm utilises ideas in capacitated graphs called the residual capacity and the residual flow. This is the potential for flow to move along particular arcs. It can be summed up as Residual Flow = Capacity – Forwards Flow + Backwards Flow. See the diagram below to see how it works (the first number is the flow, the second the capacity).

ripoffresidual

Residual capacities

What is the Augmenting Path Algorithm?

The basic idea in the augmenting path algorithm is to search for possible paths from the source node to the sink node in the graph which can carry a positive flow. This is known as an `augmenting path‘. Once we have found a path we send the maximum flow that we can along the path and then update the capacities on each arc in that path. This is where the need for residual capacities comes in. We then look for another augmenting path in the updated network and repeat the process. When no more augmenting paths can be found in the network the algorithm terminates.

networkpath

An initial augmenting path

Example: Augmenting Path (Shortest path)

This slideshow requires JavaScript.

Variants of Augmenting Path Algorithm

  • Labelling algorithm  \rightarrow O(n^2m)

This is the simplest form of the augmenting path method which is simple to implement, but it is not very efficient in practice.

  • Capacity scaling algorithm  \rightarrow O(n^3)

This is a special implementation of the algorithm and chooses to send flow along paths starting with paths with the largest residual capacity.

  • Successive-shortest path algorithm  \rightarrow O(n^2\sqrt{m})

This version is the best augmenting path algorithm and sends flow along the shortest directed paths first using the distance nodes as seen in the example above.

Drawback to Augmenting Path Algorithms

Augmenting path algorithms tend to be computationally expensive. As they send flow down paths we have to do an operation to move flow in each arc of the path. This means that there are some examples where we have to do an extremely large number of computations.

failedaugpath

Bad case for augmenting path algorithms

In the picture above we have a long sequence of high capacity arcs followed by a sets of arcs of capacity of unit 1. As a result there are clearly 5 augmenting paths through the network.

The augmenting path algorithm will then analyse the 5 paths and end up sending 1 unit flow along each of them. This reaches the correct answer but will require a lot of computations. It needs to consider 5 paths of length 7, so we have a total of 5*7=35 computations.

It would be far more efficient if we noticed that we only really need to look at the end paths with unit capacities. Whilst we need to analyse the flow along each of these short paths, we could cut out the need to analyse the paths from the start by sending all the flow we can at the start. As a result we could end up needing only 5+5*2=15 computations. This is the approach taken by pre-flow push algorithms.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s