7
\$\begingroup\$

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:

cost

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.

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Mego Feb 1 at 18:33
  • \$\begingroup\$ Golfing for a long time then realized I was golfing the wrong algorithm because I can't read \$\endgroup\$ – Quintec Feb 1 at 20:00
1
\$\begingroup\$

Wolfram Language, 42 bytes

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

Trivial builtin. Non-builtin solution coming soon.

\$\endgroup\$
1
\$\begingroup\$

R, 201 186 149 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
\$\endgroup\$
  • \$\begingroup\$ Nice, linear programming :) Unfortunately most languages don't have an lpSolve... :( \$\endgroup\$ – Quintec Feb 3 at 16:34
  • \$\begingroup\$ That's unfortunately true... BTW it's not available on base-R, it's a package... I had to ask to install on TIO ;) \$\endgroup\$ – digEmAll Feb 3 at 16:39
  • \$\begingroup\$ 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 \$\endgroup\$ – Quintec Feb 3 at 16:41
  • \$\begingroup\$ @Quintec: are you referring to a specific implementation (e.g. in a certain language) of MinCostMaxFlow ? \$\endgroup\$ – digEmAll Feb 3 at 16:45
  • \$\begingroup\$ No, my hand coded algorithm \$\endgroup\$ – Quintec Feb 3 at 16:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.