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 with weight , and be the shortest path to node (for some reasonable definition of shortest path), then .
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 algorithm. If there are any negative edges, Johnson's Algorithm defines a potential function , such that for every edge , the following holds: . Then, each edge weight can be transformed into , resulting in positive weight. This condition coincides with the Triangle Inequality, so we can arbitrarily pick a node and run a 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 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 , the source node, as the function. At each step, run Dijkstra's using the function, update the 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 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 function does not store the shortest paths, it still satisfies the triangle inequality for all edges.
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!