| Bytes | Lang | Time | Link |
|---|---|---|---|
| 669 | Python3 | 250718T200651Z | Ajax1234 |
| 144 | [R + lpSolve] | 190203T140101Z | digEmAll |
| 137 | Python 3 + NetworkX | 190225T045505Z | user4594 |
| 042 | Wolfram Language | 190201T184720Z | lirtosia |
Python3, 669 bytes
E=enumerate
G=lambda m:{(x,y):v for x,r in E(m)for y,v in E(r)if v}
def C(c,a,v,n):
q=[(0,0,[0])]
for N,T,p in q:
if N==n:yield(p,T);continue
for A,B in c:
if A==N and v<=c[(A,B)]and B not in p:q+=[(B,T+v*a[(A,B)],p+[B])]
def f(c,a,d):
n=len(c)-1
c,a=G(c),G(a)
q,r=[([],1)],[]
for i,I in q:
if sum(i)==d:r+=[i];continue
if sum(i)>d:continue
q+=[(i+[I],I)]+[(i+[I],I+1)]*(I+1<=max(c.values()))
q,F=[(c,k,0)for k in r],[]
for c,k,T in q:
if[]==k:F+=[T];continue
if F and T>=min(F):continue
if(O:=[*C(c,a,k[0],n)]):
P,W=min(O,key=lambda x:x[1]);o={**c}
for i in range(len(P)-1):o[tuple(P[i:i+2])]-=k[0]
q+=[(o,k[1:],T+W)]
return min(F)
[R + lpSolve], 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
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 -> yin 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
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.
Wolfram Language, 42 bytes
FindMinimumCostFlow[#,1,VertexCount@#,#2]&
Trivial builtin. Non-builtin solution coming soon.