Le problème du flot de coût minimum

Ici, chaque arc est muni d'un coût $c_{ij}$ dit coût unitaire par unité de flot et le problème consiste à trouver un flot $x$ sur le réseau tel que le coût du flot :

$$\sum\limits_{(\ivj)\,\in\,G} \xij \times \cij$$

soit minimal. Le plus souvent, nous serons à la recherche d'un flot maximal à coût minimal. Les algorithmes les plus performants travaillent alors en deux temps. D'une part, la recherche du flot maximal permet de fixer sa valeur. Il est alors possible, soit de rechercher ex nihilo un nouveau flot de coût minimal, soit de modifier le flot obtenu précédemment afin de le rendre minimal. Ce problème est d'une importance cruciale en recherche opérationnelle. En effet, comme nous le verrons plus tard, il sert à modéliser de nombreux cas concrets. Longtemps considéré comme un problème difficile, la démonstration de sa polynomialité par Edmonds et Karp ouvrit en son temps de nouveaux horizons en recherche opérationnelle.