Algo II - Ford-Fulkerson
mardi 8 avril 2014
11:19
Fmax = 8+2
Soit un graphe ayant des arcs de capacité C.
L'algo de Ford-F permet de trouver le chemin optimal évitant la saturation de cette capacité pour un flux F.
Il nous donne le flux max.
DEROULEMENT:
Depuis le sommet S, aller de sommet en sommet 
Toujours vérifier si le flux est strictement inférieur à la capacité avant de marquer. En chemin direct, on marque par +.
Dés qu'on arrive à P, on a une chaîne améliorante.
On prend min{eps-;eps+} eps+ si chemin direct, eps- sinon.
On prend la capacité minimale de tous les arcs de la chaîne: C'est le flux maximal pour le chemin. Pour tous les flux du chemin, on leur ajoute ce flux maximal.
On enlève les marquages, et on pose
Flux Maximal Général = FluxMax Général + FluxMax Chemin.
On réitére en repartant de S. Certains arcs sont désormais saturés(flux pleins), il faut essayer ainsi de trouver un autre chemin.
Quand on ne trouve plus de chemin direct(flux saturés) il faut faire un marquage indirect:
Choisir un arc non marqué et avec un flux non nul et le marquer par - 
Une fois le flux maximal du chemin calculé, pour tous les flux marqués d'un -, on leur soustrait ce flux maximal.
Fmax = 0+8
Fmax=10+4=14