[
]

# Minimum Cost Maximum Flow: Cycle Cancelling Algorithm

**Minimum Cost flow problem** is a way of minimizing the cost required to deliver maximum amount of flow possible in the network. It can be said as an extension of **maximum flow problem** with an added constraint on *cost* (per unit flow) of flow for each edge.

## Algorithm (Pseudocode)

```
def CostNetwork(Graph G, Graph Gf):
Gc <- empty graph
for i in edges E:
if E(u,v) in G:
cf(u,v) = c(u,v)
else if E(u,v) in Gf:
cf(u,v) = -c(u,v)
def MinCost(Graph G):
Find a feasible maximum flow of G and construct residual graph Gf
Gc = CostNetwork(G, Gf)
while(negativeCycle(Gc)):
Increase the flow along each edge in cycle C by minimum capacity in the cycle C
Update residual graph(Gf)
Gc = CostNetwork(G,Gf)
mincost = sum of Cij*Fij for each of the flow in the graph
return mincost
```

Note 1: To find a feasible maximum flow of $G$, use Ford Fulkerson’s Algorithm.

```
def FordFulkerson(Graph G, Node S, Node T):
Initialise flow in all edges to 0
while (there exists an augmenting path(P) between S and T in residual network graph):
Augment flow between S to T along the path P
Update residual network graph
return
```

Note 2: To find a negative cycle in graph $G_c$, use Bellman Ford’s Algorithm

For a more detailed lecture, please refer to http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/mincost.4up.pdf.