 Cycle Cancelling Algorithm  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.

## Legende Node Edge with capacity 10 and cost 1

## Which graph do you want to execute the algorithm on?

### 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.

A occured when reading from file: the contents:

## Legende Node S/T node Edge with flow 7, cap 10 and cost 1 Edge in residual graph, cost 1 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.

### Finished

The algorithm terminated!

s ← pick(v)

t ← pick(v)

BEGIN

(* Initialize to max flow *)

CALCULATE MAX FLOW

(* Main Loop *)

WHILE negative cycle might exist DO

EXECUTE BELLMAN-FORD

IF negative cycle exists

IDENTIFY cycle-edges

e ∈ cycle-edges)

FOR e ∈ cycle-edges