Un cas simple de décomposition en plusieurs sous-problèmes

Considérons le graphe suivant :

 

Figure 4.2: Le coût des arcs du graphe

Les sources sont 5, 6, 7 et proposent 10. Les puits sont 1, 2, 4 et demandent 10.

Le problème se décompose en trois sous-problèmes. On obtient tout de même la solution :

 

Figure 4.3: La solution optimale

Le coût de cette solution est 20 + 10 + 10 = 40