Minimum-cost flow problem

In the minimum-cost flow problem, we want to find a flow that satisfies all supply and demand and has the minimum possible cost. Formally, a flow in the network $G$ is a function $f:E\to R$ assigning flows to edges, $f(v,w)$ (non-negative amount of flow on edge $v$ to $w$), which satisfies the capacity constraints and flow conservation constraints.

The input is a flow network $G=(V,E,u,c,d)$ where:

• $V$ is a set of nodes
• $E$ is a set of directed edges
• For each edge $(v,w)\in E$, $u(v,w)\ge 0$ is the capacity of edge $(v,w)$ We label each edge (x, y)
• For each node $v\in V$, (as in flow-feasibility problem) $|d(v)|$ is the (initial) supply (if $d(v)>0$) or demand (if $d(v)<0$) at $v$. 1st number on each edge, x ${\sum }_{v\in V}d(v)=0$
• For each edge $(v,w)\in E$, $c(v,w)\ge 0$ is the cost of one unit of flow on edge $(v,w)$. 2nd number on each edge, y