120
Recherche opérationnelle
Etape c
Pour tout
Lorsque
, tous les
sont égaux aux
et donnent donc les valeurs du plus court
chemin entre
.Pour avoir le chemin le plus court lui même il faut repérer à partir
de quel sommet la valeur a été calculée, puis le sommet à partir duquel la valeur
a été calculée etc.
Exemple : Soit le graphe suivant, où les valeurs des arcs sont indiquées sur ces derniers
(figure 9)
Figure 8
L'algorithme de Moore-Dijkstra donne les opérations suivantes:
)
,
(
=
ji
j
i
i
l
min
1
2
4
5
7
3
6
8
9
10
3
4
2
2
1
3
3
3
3
3
2
2
2
2
1
1
1