Minimum cost flow

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved very efficiently using the network simplex algorithm.

A flow network is a directed graph ${\displaystyle G=(V,E)}$ with a source vertex ${\displaystyle s\in V}$ and a sink vertex ${\displaystyle t\in V}$, where each edge ${\displaystyle (u,v)\in E}$ has capacity ${\displaystyle c(u,v)>0}$, flow ${\displaystyle f(u,v)\geq 0}$ and cost ${\displaystyle a(u,v)}$, with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge ${\displaystyle (u,v)}$ is ${\displaystyle f(u,v)\cdot a(u,v)}$. The problem requires an amount of flow ${\displaystyle d}$ to be sent from source ${\displaystyle s}$ to sink ${\displaystyle t}$.

...
Wikipedia