Cycle-canceling algorithm

The algorithm starts with a maximum flow resolution. Then, iteratively, the algorithm looks for a cycle with a negative cost (negative cost if the edge is taken in the opposite direction of the flow) and increases the flow on this cycle. When there is no more negative cycle, the algorithm ends.

Example :

cca1

Let’s construct the residual graph and look for a negative cycle:

cca2

The cycle  4-2-3-4 has a cost of -3 + 1 + 1 = -1, we saturate it with a flow of 2.

The cycle 4-2-1-3-4 has a cost of -3 -2 +2 +1 = -2, we saturate it with a flow of 1.

There is no more negative cycle. The algorithm ends.

 

Publicités