Algorithme de calcul du flot maximum

[thedream01]

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

[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

[thedream01]

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

[Patastronch]

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

[thedream01]

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

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

[Patastronch]

C'est ce que j'ai fait...
Mais par exemple pour ce site:
http://www.math-info.univ-paris5.fr/~seret/Algo5-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.

[thedream01]

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

[Patastronch]

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.