Problèmes de chemins
127
À partir de 8 :
À partir de : inchangé.
Le chemin de valeur minimale est donc :
Il est indiqué en trait renforcé sur la figure. Il est obtenu en remontant à partir de 10
comme l'indique la procédure.
4
1
1
4
3
4
4
3
6
3
3
6
8
6
6
8
10
8
8
10
1
=
2
=
1
=
1
=
1
=
2
=
1
=
2
=
1
=
1
=
A cause de la possibilité de retourner en arrière, la complexité de cet algorithme est en
. ( nombre de sommets, nombre d'arcs)
Remarquons qu'il est plus simple de repérer, lorsqu'un
diminue, quel est le sommet i
qui a contribué à cette diminution. On a alors le chemin cherché immédiatement.
Les retours en arrière tels que ceux que l'on a constatés sur l'exemple traité peuvent être
très gênants au niveau du temps de calcul. Pour pallier cet inconvénient, il est toujours
possible de réorganiser le graphe (à condition qu'il soit sans circuit) de façon que ces
retours en arrière ne soient pas possibles.
Par exemple le graphe traité de la figure 8 peut se représenter de la façon suivante :
Figure 10
I
II
III
IV
V
VI
VII
1
2
3
7
6
5
0
8
10
9
4