PROBLEME DU FLOT DE COUT MINIMAL:
ALGORITHME DE BUSACKER ET GOWEN

 

Cet algorithme permet de calculer le flot maximal au coût minimal dans un graphe dont les arcs sont munis d'une capacité j et d'un coût a.

Le problème à résoudre est le suivant:

Calculer le minimum de S a(u)j (u), sachant que le flot maximal j0 pouvant circuler dans le graphe est égal à une certaine valeur V0.

Enoncé de l'algorithme

min Su a(u)j (u)
Aj = 0
0 £ j u £ Cu
pour tout u Î U
j o = Vo ( flot maximal )
j = 0

1) a' (x, y) = a(x, y) si j (x, y) < C(x, y)

2) a' (x, y) = ¥ si j (x, y) = C(x, y)
a' (y, x) = -a(x, y) si j (x, y) > 0
C(y, x) = j (x, y) si j (x, y) > 0

3) Chercher le PCCH de S à P, les longueurs des arcs étant les coûts modifiés a'.

Si sa longueur est infinie
STOP:
il est impossible de trouver un flot de valeur Vo de S à P.

Sinon
Soit j M = Min { C(x, y) - j (x, y) }
                             PCCH
D j = Min { Vo - j , j M }
j ¬ j + D j

4) Si j o = Vo
STOP : le flot optimal est trouvé.

Sinon, aller en 2.


Retour en haut de page