Rare
0/7

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

## 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)	{

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

## Problems

StatusSourceProblem NameDifficultyTags
CFNormal
Show TagsMCF
CFNormal
Show TagsMCF
CFNormal
CFHard
CFVery Hard
CFVery Hard

## Applications

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

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

Resources
Wikipedia
Topcoder

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

More hungarian alg problems

StatusSourceProblem NameDifficultyTags
CFHard

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