4.5 Flot de valeur maximale à coût mini mal
137
© Dunod – Toute reproduction non autorisée est un délit.
La déter mi na tion d’un che min de coût mini mal peut se faire en uti li sant l’algo -
rithme de Ford pré senté plus haut. Le lecteur remarquera que le cal cul des nou veaux
flux sur le che    min C se fait de manière ana logue à celle pré sen tée dans le para graphe
pré    cé    dent consa    cré aux flots de valeur maximale.
La figure 4.27 illustre sur l’exemple pré    cé    dent le dérou    le    ment de l’algo    rithme. 
Les flèches épaisses cor    res    pondent, ici à chaque étape, au che    min de coût mini    mal 
de S vers P. (et non pas à des arcs saturés, comme plus haut).
Figure 4.27 Une exé cu tion de l’algo rithme de Roy- Busacker-Gowen
Remar    quons enfin, en reve    nant au pro    blème de flot de valeur maximale, que l’on peut 
aisé ment refor mu ler l’algo rithme de Ford- Fulkerson en termes de graphe d’écart :
soit f
(0)
 le flot ini   
tial.
1. Poser f d f
102
. Pour tout arc u 5 (x, y) du réseau de transport, poser v(u)
d w (x, y) .
2. Construire le graphe d’écart G
e
(f) (comme dans le Fig. 4.25).
3. Tant que G
e
(f) com porte un che min de s vers p
4. choi sir un tel che min, soit : m
poser e 5 min
uPm
v(u) ;
5. pour tout arc u 5 (x, y) du che min m faire
v1 x, y2 d v1 x, y2 2 e ; si v1 x, y2 5 0, sup pri mer l’arc u dans G
e
1 f2 ;
v(y, x) d v(y, x) 1 e ; si v(y, x) était nul, ajou ter u dans G
e
1 f2
Voici un exemple du pro    blème de flot de valeur maximale, ci­      dessous, avec un 
flot ini    tial  (arbi    traire) f
(0)
, traité par l’algo rithme de Ford- Fulkerson refor mulé en
termes de graphe d’écart :