# Minimum-cost flow problem

A flow network is a directed graph G = (V, E) with a source vertex s ϵ V and a sink vertex t ϵ V, and where every edge (u, v) ϵ E on the graph (connecting nodes u ϵ V and v ϵ V) has 2 quantities associated with it:

1. c(u, v) >= 0, the capacity of the edge
2. a(u, v) >= 0, the cost of sending one unit through the edge

We define a function 0 <= f(u, v) <= c(u, v) to be the number of units being passed through a given edge (u, v). Thus, the cost for a given edge (u, v) is a(u, v) * f(u, v). The minimum-cost flow problem is defined as minimizing the total cost over all edges for a given flow amount d, given by the following quantity:

The following constraints apply to the problem:

1. Capacity requirements: the flow through a given edge may not exceed the capacity of that edge (f(u, v) <= c(u, v)).
2. Skew symmetry: the flow though a given edge must be antisymmetric when the direction is reversed (f(u, v) = -f(v, u)).
3. Flow conservation: the net flow into any non-sink non-source node must be 0 (for each u ∉ {s, t}, summing over all w, sum f(u, w) = 0).
4. Required flow: the net flow out of the source and the net flow into the sink must both equal the required flow through the network (summing over all u, sum f(s, u) = sum f(u, t) = d).

Given a flow network G and a required flow d, output the minimum cost for sending d units through the network. You may assume that a solution exists. d and all capacities and costs will be non-negative integers. For a network with N vertices labeled with [0, N-1], the source vertex will be 0 and the sink vertex will be N-1.

This is , so the shortest answer (in bytes) wins. Remember that this is a competition within languages as well as between languages, so don't be afraid to post a solution in a verbose language.

Built-ins are allowed, but you are encouraged to include solutions without builtins, either as an additional solution in the same answer, or as an independent answer.

Input may be in any reasonable manner that includes the capacities and costs of each edge and the demand.

## Test Cases

Test cases are provided in the following format:

c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>

c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213


These test cases were computed with the NetworkX Python library.

• Sandbox
– user45941
Commented Feb 1, 2019 at 18:33
• Golfing for a long time then realized I was golfing the wrong algorithm because I can't read Commented Feb 1, 2019 at 20:00

# [R + lpSolve], 201186149 144 bytes

function(c,a,d,^=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))\$objv


Try it online!

The code constructs the following Linear Problem and solve it using lpSolve package :

\begin{align} min & \sum_{\forall x \in V}\ \sum_{\forall y \in V} A_{x,y} \cdot f_{x,y} \\ subject\ to : & \\ & \sum_{x \in V} f_{v,x} - f_{x,v} = 0 & \forall v \in V : v \neq \{s,t\} \\ & \sum_{x \in V} f_{s,x} - f_{x,s} = d \\ & \sum_{x \in V} f_{t,x} - f_{x,t} = -d \\ & f_{x,b} \leq C_{x,b} & \forall x \in V,\forall y \in V \end{align} where :

• $$\V\$$ is the set of vertices
• $$\s\$$ s is the source vertex
• $$\t\$$ s is the target (or sink) vertex
• $$\A_{x,y}\$$ is the flow cost for edge x -> y
• $$\f_{x,y}\$$ is the flow of edge x -> y in the optimal solution
• $$\d\$$ is the required flow at sink (i.e. the demand at $$\t\$$ and the production at $$\s\$$)
• $$\C_{x,y}\$$ is the maximum capacity of edge x -> y
• Nice, linear programming :) Unfortunately most languages don't have an lpSolve... :( Commented Feb 3, 2019 at 16:34
• That's unfortunately true... BTW it's not available on base-R, it's a package... I had to ask to install on TIO ;) Commented Feb 3, 2019 at 16:39
• For some reason I have yet to find a short way of modifying MinCostMaxFlow to become MinCostFlow... my brain is fried lol, I wish there was a function for this in languages other than mathematica Commented Feb 3, 2019 at 16:41
• @Quintec: are you referring to a specific implementation (e.g. in a certain language) of MinCostMaxFlow ? Commented Feb 3, 2019 at 16:45
• No, my hand coded algorithm Commented Feb 3, 2019 at 16:46

# Wolfram Language, 42 bytes

FindMinimumCostFlow[#,1,VertexCount@#,#2]&


Trivial builtin. Non-builtin solution coming soon.

• Is it coming in 6-8 weeks? :P Commented Feb 25, 2019 at 14:54

# Python 3 + NetworkX, 137 bytes

from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)


No TryItOnline link because TIO doesn't have the NetworkX library installed

Takes graph input as an edge list with capacity and weight attributes, like this:

[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]


This is a golfed version of the code that I used to verify the test cases.