A maximum flow Cycle Cancelling Algorithm Technische Universität München

The min-cost flow does not use the expensive edge with cost 3.

The Min-Cost Flow Problem

Road system, water pipes, or data networks are the motivation for a class of optimisation problems termed flow problems. The shared characteristic for this type of system is that some kind of resource has to be transported over the edges of a graph, which are constrained to only carry only up to a certain amount of flow. For some instances edges also have other properties, making it useful to assign a cost for using a specific edge - for example variable toll charges in a network of highways.

In this kind of setting it is interesting to compute how a certain flow can be routed through the network using the cheapest possible route. This problem is called the minimum-cost flow problem.

This applet presents the cycle cancelling algorithm to calculate a minimum-cost flow on a given network.

What do you want to do first?


node Node
edge Edge with capacity 10 and cost 1


Which graph do you want to execute the algorithm on?

Start with an example graphs:

Modify it to your desire:

  • To create a node, double-click in the drawing area.
  • To create an edge, first click on the output node and then click on the destination node.
  • The edge weight can be changed by double clicking on the edge.
  • Right-clicking deletes edges and nodes.

Download the modified graph:


Upload an existing graph:


occured when reading from file:

the contents:


What next?


node Node
node S/T node
edge Edge with flow 7, cap 10 and cost 1
edge Edge in residual graph, cost 1
edge Edge on negative cycle, cost 1


Algorithm status

First choose a source node

Click on a node to select it as the source/starting node s

Then choose a target node

Click on a node to select it as the target/sink node t

Cycle cancelling flow algorithm

Now the algorithm can begin. Click on next to start it

Initializing the flow

Computes the maximal possible flow while ignoring the cost information

Entering the main loop

The main loop repeatedly identifies negative cycles in the residual graph.

Find a negative cycle

By running the Bellman-Ford algorithm we check for a negative cost cycle in the residual graph.

Cancel Cycle

The negative cycle is removed from the residual graph by saturating one of the edges.


The algorithm terminated!

s ← pick(v)

t ← pick(v)


(* Initialize to max flow *)


(* Main Loop *)

WHILE negative cycle might exist DO


IF negative cycle exists

IDENTIFY cycle-edges

adjustment ← min(cost[e] |

e ∈ cycle-edges)

FOR e ∈ cycle-edges

flow[e] += adjustment


Variable State

cycle adjustment
- -

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.