Rare
0/7

# Minimum Cost Flow

Authors: Siyong Huang, Benjamin Qi

### Prerequisites

• Platinum - Maximum Flow

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

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 $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 $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 $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-AlgorithmsNote: Does not use optimal solution, but explains the concept well.
TopCoder

## Implementation

With all this being said, here is my implementation.

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

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

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CFNormal
Show Tags

MCF

Check CF
CFNormal
Show Tags

MCF

Check CF
CFNormalCheck CF
CFHardExternal Sol
CFVery HardCheck CF
CFVery Hard

## Applications

### This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

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

Resources
Wikipedia
Topcoder

### This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

More hungarian alg problems

StatusSourceProblem NameDifficultyTagsSolution
CFHardCheck CF