Algorithme de Busacker et Gowen
On considérera par la suite que le graphe $G$ est antisymétrique puisque l'on utilise des graphes d´écart. On a vu que ce n'était pas restrictif puisque l'on peut associer un graphe antisymétrique à tout graphe en ne changeant pas les valeurs de flots
Si on doit payer un coût pour faire transiter un flot par un arc, il est naturel de rechercher un flot maximum à coût minimum.
Définition
Si $\gamma : E \rightarrow \mathbb{R}^+$ est une fonction de coût sur les arc de $G$ et $f$ un de ses flot, le coût du flot est :
Le problème est alors :
Parmi tous les flot maximum, un choisir un de coût minimum.
Ce qui est surprenant, c'est que ceci peut se faire aisément en modifiant l'algorithme de Edmonds et Karp : plutôt que de chercher un chemin de longueur minimum dans le graphe d'écart, on cherche un chemin de coût minimum en utilisant la fonction de coût suivante :
- si $xy$ est un arc de $G$ on le coût de l'arc dans le graphe d'écart est le même que pour le graphe d'origine puisque si cet arc est choisi on va augmenter le flot passant par lui
- si $xy$ est un arc de $G$ on le coût de l'arc dans le graphe d'écart est l'opposé du coût dans le graphe d'origine puisque si cet arc est choisi on va diminuer le flot passant par lui
Comme les poids peuvent être négatifs, il faut utiliser l'algorithme de Belman-ford de complexité $\mathcal{O}(e(G) \cdot v(G))$ pour trouver un chemin de longueur minimum entre $s$ et $t$.
Enfin, il faut partir du flot nul pour que l'optimalité soit garantie.
Cet algorithme est appelé algorithme de Busacker-Gowen.
Cela semble une amélioration naturelle mais la justification de sa véracité ne l'est pas vraiment.
Véracité
TBD voir le charon-Hudry p251 (partie 11.5)
Complexité
TBD peut-on se ramener à avoir uniquement des poids positifs ? voir bouquin network flows.
La recherche d'un chemin de coût min n'est plus en $\mathcal{O}(e(G))$ mais en $\mathcal{O}(e(G) \cdot v(G))$. Une recherche de chemin puis une augmentation du flot est donc en $\mathcal{O}(e(G) \cdot v(G))$ opérations.
Comme on augmente un flot de coût minimum, on a plus de garantie de polynomialité comme pour l'algorithme de Edmonds-Karp, la seule borne que l'on a est celle de l'algorithme de Ford et Fulkerson : on peut faire au maximum $c(S, \overline{S})$ itérations avec $S$ une coupe quelconque.
Proposition
La complexité de l'algorithme de Buscker-Gowen est en $\mathcal{O}(c(S, \overline{S}) \cdot e(G) \cdot v(G))$ opérations.
Si l'on cherche des algorithmes polynomiaux pour résoudre ces problème on peut utiliser des méthodes de programmation linéaire, mais ceci sort du cadre d'un court de graphe.