next up previous
suivant: Le problème des arbres monter: L'algorithme de Ford & précédent: Une implémentation possible de

Une amélioration possible

Il est possible d'ameliorer significativement les performances de l'algorithme de Ford & Fulkerson en mettant à profit une idée de Edmonds & Karp :
Plutôt que de choisir un chemin augmentant au hasard, il faut systématiquement considérer le plus court chemin de $ s$ vers $ t$ au sens du nombre d'arcs dans le chemin.
Cette modification garantit la terminaison de l'algorithme sur tout réseau non dégénéré !

Bruno Garcia 2000-12-17