Recherche d’un parcours dans un flot existant

Ce problème est apparenté à un problème de flot maximum ou de flot à coût minimum. A partir d’un graphe, il est possible de déterminer le chemin d’un nouveau flot de capacité de au moins 1 d’un sommet i à un sommet j du graphe. Pour cela il faut suivre la démarche suivante :

  • Après avoir calculer le flot, pour tous les arcs faire new_capacité_max = (capacité_max – flot_existant). Le nouveau graphe est nommé G’.
  • Sur G’, retirer les sources et les puits existants (non obligatoire).
  • Rajouter une source de capacité 1 vers le noeud i.
  • Rajouter un puits de capacité 1 du noeud j.
  • Calculer le flot maximum (il ira bien de i à j s’il existe).
Publicités