# Minimum Cost Flow

Authors: Siyong Huang, Benjamin Qi

Triangle Inequality, Johnson's Algorithm, and Min Cost Flow

### Prerequisites

In this section I will briefly walk over my understanding of min cost flow. I would highly recommend reading through CP-Algorithm's Min Cost Flow to understand the solution idea first. Additionally, check the TopCoder tutorial for a more detailed explanation.

## Triangle Inequality

In graph theory, the **Triangle Inequality** states that if there is an edge
$u \rightarrow v$ with weight $w$, and $d_k$ be the shortest path to node $k$
(for some reasonable definition of shortest path), then $d_v - d_u \leq w$.

Resources | ||||
---|---|---|---|---|

Wikipedia | Mainly in geometry, but it has the gist of the idea. |

## Johnson's Algorithm

The main idea of **Johnson's Algorithm** is that if all edge weights are
positive, then running Dijkstra's from each node would result in a
$\mathcal{O}(VE \log E)$ algorithm. If there are any negative edges, **Johnson's
Algorithm** defines a potential function $\pi$, such that for every edge
$u,v,w$, the following holds: $w>=\pi(u)-\pi(v)$. Then, each edge weight can be
transformed into $w \rightarrow w + \pi(v)-\pi(u)$, resulting in positive
weight. This condition coincides with the **Triangle Inequality**, so we can
arbitrarily pick a node and run a $\mathcal{O}(VE)$ shortest path algorithm to
determine this function.

Resources | ||||
---|---|---|---|---|

GFG | ||||

Wikipedia |

## Minimum Cost Flow

The general idea of Min Cost Flow is to repeatedly push flow along the shortest
path. Since flow graphs have negative edges, each step naively would take
$\mathcal{O}(VE)$ time. To speed it up, we can use the same potential function
from **Johnson's Algorithm** to employ Dijkstra for this process. In this case
we *must* use distance from $S$, the source node, as the $\pi$ function. At each
step, run Dijkstra's using the $\pi$ function, update the $\pi$ function to
match the current distances, and then push flow along the shortest path,
reversing edges as needed. Once flow is met or the sink is unreachable,
terminate.

### Important Clarification

Note that the $\pi$ function stores values *before* the edge reverses happen.
Luckily the **triangle inequality**'s equality case is along the shortest path,
meaning that in a flow network it holds both forwards and backwards along edges
in the shortest path. This means that although the $\pi$ function does not store
the shortest paths, it still satisfies the **triangle inequality** for all
edges.

$\pi(u)-\pi(v)=w \implies \pi(v)-\pi(u)=-w$

Resources | ||||
---|---|---|---|---|

CP-Algorithms | Note: Does not use optimal solution, but explains the concept well. | |||

TopCoder |

## Implementation

With all this being said, here is my implementation.

template <int MN, int MM>struct MCF // MN = nodes, MM = edges [assume edges one-directional]{public:int N, M, S, T;int flow[MM * 2], cap[MM * 2], hd[MN], nx[MM * 2], to[MM * 2], cost[MM * 2];int pi[MN], p[MN], d[MN];int vis[MN];void init(int n, int s, int t) {N = n, S = s, T = t;

Also check out Benq's Implementation and KACTL's Implementation (which are a lot better than mine).

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Normal | ## Show TagsMCF | |||

CF | Normal | ## Show TagsMCF | |||

CF | Normal | ||||

CF | Hard | ## Show TagsBitmasks, MCF | |||

CF | Very Hard | ||||

CF | Very Hard |

## Applications

### Assignment Problem

### This section is not complete.

Better resources? I honestly just found some that came up in a google search.

Resources | ||||
---|---|---|---|---|

Wikipedia | ||||

YouTube - Algorithms Thread | ||||

Topcoder |

### This section is not complete.

More hungarian alg problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Hard |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!