8.1 L'algorithme de Dijkstra
151
FIGURE 8.3 - On prend ensuite une feuille avec g minimal et on la développe.
FIGURE 8.4 - On continue à développer les feuilles de g minimal en évitant les positions
déjà visitées.
Exercice : É crire un programme qui calcule le plus court chemin entre deux points
sur une carte à l'aide de l'algorithme de Dijkstra. On s'attachera à utiliser des structures
de données efficaces qui permettront de trouver le plus court chemin avec une complexité
linéaire en fonction de la taille de la carte.
151
FIGURE 8.3 - On prend ensuite une feuille avec g minimal et on la développe.
FIGURE 8.4 - On continue à développer les feuilles de g minimal en évitant les positions
déjà visitées.
Exercice : É crire un programme qui calcule le plus court chemin entre deux points
sur une carte à l'aide de l'algorithme de Dijkstra. On s'attachera à utiliser des structures
de données efficaces qui permettront de trouver le plus court chemin avec une complexité
linéaire en fonction de la taille de la carte.