150
Recherche de plus court chemin sur une carte
D
FIGURE 8.1 - On cherche le plus court chemin entre D et A.
g=I
FIGURE 8.2 - On insère dans les positions à développer tous les fils de la position de
départ.
velopper la position non encore développée qui a un g minimal. Dans notre cas, toutes
les positions aux feuilles (c'est à dire non encore développées) ont un g = 1 . Il choisit la
première feuille et la développe comme indiqué en figure 8.3.
On peut noter que l'algorithme ne développe pas le déplacement vers la droite car il
amène à une position déj à visitée. Nous nous retrouvons maintenant avec un arbre qui
comporte des feuilles avec g = 2 et des feuilles avec g = 1. Le principe de l'algorithme
étant de développer les feuilles de g minimal, il développe alors une feuille avec g = 1 ,
comme indiqué en figure 8.4.
Lorsqu'on continue l'algorithme, il ne reste qu' une seule feuille avec g = 1 , c'est
donc celle là qui est développée en figure 8.5.
L' algorithme continue ainsi jusqu'à visiter la position d'arrivée et à s'assurer que
toutes les feuilles de l'arbre ont un g supérieur ou égal au g de la position d'arrivée.
Exercice : Continuer le développement de l'algorithme après la figure 8.5 et vérifier
qu'il trouve bien le plus court chemin.
L' algorithme de Dijkstra pour les cartes est donné dans l'algorithme 6.