Minimum-cost flow problem: Difference between revisions

Revision as of 05:33, 27 September 2021

Revision as of 19:41, 28 April 2022

Line 5:

== Definition ==

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

The definition of the problem is to minimize the '''total cost''' of the flow over all edges: