Problème du flot maximum

Introduction à l'Algorithmique
L3 ENS Rennes, Mardi 14 novembre 2017

Emmanuel Caruyer
VisAGeS Research Team
CNRS - IRISA (UMR 6074)
Inria Rennes - Bretagne Atlantique
Inserm U746

Tentative d'une stratégie gloutonne

Tentative d'une stratégie gloutonne

On débute avec un flot vide, \(f\)

Tentative d'une stratégie gloutonne

On débute avec un flot vide, \(f\)
Puis on cherche un chemin (quelconque) de \(s\) à \(t\).

Tentative d'une stratégie gloutonne

On débute avec un flot vide, \(f\)
Puis on cherche un chemin (quelconque) de \(s\) à \(t\).
On « ajoute » ce chemin à \(f\) et on le « retire » à \(c\).

Tentative d'une stratégie gloutonne

On débute avec un flot vide, \(f\)
Puis on cherche un chemin (quelconque) de \(s\) à \(t\).
On « ajoute » ce chemin à \(f\) et on le « retire » à \(c\).
Puis on réitère.

Tentative d'une stratégie gloutonne

On débute avec un flot vide, \(f\)
Puis on cherche un chemin (quelconque) de \(s\) à \(t\).
On « ajoute » ce chemin à \(f\) et on le « retire » à \(c\).
Puis on réitère.

Tentative d'une stratégie gloutonne

Tentative d'une stratégie gloutonne - Échec

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson

Algorithme de Ford-Fulkerson