118
Recherche opérationnelle
Il existe à l'heure actuelle de nombreux algorithmes traitant ce problème. Nous
n'exposerons ici que les plus connus d'entre eux.
Nous distinguons deux cas: celui où
pour tout (qui est à dire vrai le cas le
plus courant en recherche opérationnelle) et le cas
où est de signe quelconque.
Algorithme 1 :
Algorithme de Moore-Dijkstra.
Cet algorithme permet de déterminer le plus court chemin entre un sommet particulier
d'un graphe
, aux valeurs d'arcs positives ou nulles, et tous les autres
sommets.
Par commodité, nous appellerons les sommets du graphe
Nous nommerons
la valeur de l'arc reliant à .S'il n'y a pas d'arc entre et ,
.
Soit
la valeur du chemin le plus court entre
L'algorithme consiste à trouver
en affectant à chaque sommet une valeur provisoire
qui se stabilise en un nombre
d'itérations finies à la valeur .
Pour cela, nous séparerons, à chaque itération, l'ensemble des sommets en deux parties
et
, avec
S : ensemble des tels que
avec
. ( Pour ces sommets on a trouvé la valeur
du plus court chemin).
: on n'est pas certain pour ces sommets que
mesure la valeur du chemin le plus
court entre
, mais on fait systématiquement :
Donc, pour
donne la valeur du chemin le plus court entre
, tel que
tous les sommets de ce chemin excepté i sont dans S.
L'algorithme repose alors sur le lemme suivant:
Lemme
Soit
Alors