algorithme de calcul du flot maximum

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: thedream01

Bonjour!
Est-ce que quelqu'un pourrait m'expliquer cet algorithme svp?!(algorithme de ford-fulkeson)
merci


Posted by: Patastronch

Dit plutot quelle etape t'achappe dans l'algo, ca evitera de se perdre dans une explication sans fin.

Rappel vulgaire de l'algo :

1/ Recherche d'un flot quelconque initial qui respecte les contraintes
2/ Etape de marquage (permet de verifier si le flot est max ou pas)
3/ Augmentation du flot par deplacement de flux et retour a l'etape 2


Posted by: thedream01

Le problème est que je n'ai pas d'exemples!
Je voudrai bien avoir un exemple avec les étapes détaillées...


Posted by: Patastronch

tapes "ford-fulkeson" dans google, a mon avis tu trouveras facilement des exemples déroulés. Cet algo est un grand classique.


Posted by: thedream01

C'est ce que j'ai fait...
Mais par exemple pour ce site:
http://www.math-info.univ-paris5.fr...lgo5-cours4.pdf

Je ne comprends pas le passage du diapo 6 à 7! C'est quoi le 2?


Posted by: Patastronch

Citation:
Posté par thedream01
C'est ce que j'ai fait...
Mais par exemple pour ce site:
http://www.math-info.univ-paris5.fr...lgo5-cours4.pdf

Je ne comprends pas le passage du diapo 6 à 7! C'est quoi le 2?


Vois le graph comme un reseau de plomberie, où les couts sur les arcs sont le débit max de flotte qu'on peut faire passer.
La il recherche un flot de départ compatible avec les contraintes des arcs, pour commencer, il fait passer un débit de 2 sur le chemin du haut, rien de plus. Pourquoi il met pas plus que 2? parceque sur ce chemin, l'un des arcs (E,H) limite le flot a 2.


Posted by: thedream01

les chemins sont choisis de façon aléatoires?
Et C'est quoi les lettres qu'on a rajouté sur le diapo 10?


Posted by: Patastronch

Citation:
Posté par thedream01
les chemins sont choisis de façon aléatoires?
Et C'est quoi les lettres qu'on a rajouté sur le diapo 10?


Non pour trouver un flot initial tu procedes comme suit :
Cherche un chemin qui relit la source et le puit, fait passer un flot valant le min du cout des arcs sur le chemin.
Tu refait ca autant de fois que tu le désire (enretirant a chaque cout des arcs du chemin la valeur de ton flot) et t'obtiens un flot initial. Si tu fais cette étape jusqu'a que tu ne puisse plus trouver de chemin, dans ce cas la tu part d'une bonne solution initiale et le deroulement de l'algo sera plus rapide.

Les lettres c'est pour la phase de marquage. Ca va permetre de dire ou y a encore possibilité d'augmenter un flot et ou il faudrait les diminuer pour optimiser notre flot global.

Dans le transparent 3 ils t'expliquent comment sont marqué les sommets.










-