L'algorithme

L'initialisation
Pour pouvoir utiliser l'algorithme, il faut avoir un arbre solution initial. Pour trouver un tel arbre, on utilise le même algorithme. On part d'un arbre solution dont les arcs sont : (1,k) de poids P si k est un puits de P marchandises ou si P = 0 et (k,1) de poids P si k est une source de P marchandises. Mais il est bien sûr possible que ces arcs n'appartiennent pas au graphe original. On lui rajoute ces arcs fictifs avec un coût 1 et on donne aux arcs réels un coût 0. On applique l'algorithme à ce nouveau problème.

 

Figure: Arbre de départ de l'initialisation pour le premier exemple

Le problème est résolvable si et seulement si le coût de l'arbre obtenu est 0. Si l'arbre ne possède aucun arc fictif, cet arbre est un arbre d'initialisation, du problème, sinon on décompose le problème en plusieurs sous-problèmes (voir figure 3.3).

 

Figure: Décomposition en trois sous-problèmes

Remarque
L'arbre de départ est un bon arbre. Les arbres d'initialisation obtenus sont donc tous des bons arbres.

Le coût des nuds
Le calcul des c[i] se fait facilement grâce au tableau des successeurs s.

Choix de l'arc entrant
Pour trouver un arc entrant, on teste un après l'autre les arcs ne faisant pas partie de l'arbre. C'est la phase la plus coûteuse en temps.

Choix de l'arc sortant
La détection du cycle est aisée grâce aux tableaux p et d. Il faut ensuite suivre la tactique anti-cyclage vue précédemment pour choisir l'arc sortant.

Mise à jour de l'arbre
Une fois les arcs entrants et sortants déterminés, il ne reste plus qu'à mettre à jour l'arbre. Ceci représente la phase la plus complexe au niveau algorithmique. Voici une itération pour le premier exemple :

 

Figure 3.4: L'arc (2,1) entre, l'arc (2,4) sort

 

Figure: L'arbre mis à jour

La représentation de ce nouvel arbre est la suivante :

i	1	2	3	4	5	6	7
p	/	1	2	1	1	1	2
poid	/	9	6	10	8	9	15
sens	/	0	1	1	1	0	0

i	1	2	3	4	5	6	7
d	0	1	2	1	1	1	2

i	1	2	3	4	5	6	7
s	2	3	7	5	1	4	6

Voyons encore un autre exemple un peu plus général pour mieux voir les modifications, particulièrement celles du tableau s. Considérons l'arbre suivant :

Le tableau s correspondant est le suivant :

i	1	2	3	4	5	6	7	8	9	10	11	12
s	2	3	4	5	6	7	9	1	10	12	8	11

Supposons que l'arc (3,10) entre. Alors l'arc (5,7) sort. On obtient :

Le tableau s correspondant est à présent :

i	1	2	3	4	5	6	7	8	9	10	11	12
s	2	3	10	5	6	8	9	1	11	12	4	7