problème du flot de coût minimum

En théorie des graphes, le problème du flot de coût minimum est le problème algorithmique qui consiste à trouver la manière la plus économe d'utiliser un réseau de transport tout en satisfaisant les contraintes de production et de demande des nœuds du réseau. Il permet de modéliser tout un ensemble de problèmes pratiques dans lesquels il s'agit de trouver une manière optimale d'acheminer une ressource (par exemple un fluide, de l'électricité) d'un ensemble de sources à un ensemble de puits. Le problème du flot de coût minimum est fondamental dans la mesure où la plupart des autres problèmes de flots, comme le problème de flot maximum, peuvent en être vus comme des cas particuliers. De plus, il est possible de résoudre le problème dans certains cas de manière efficace en utilisant l'algorithme du simplexe pour les réseaux.