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