Visualiseur d'algorithmes de recherche de chemin
L'algorithme de Dijkstra et A* trouvent tous deux les plus courts chemins, mais explorent très différemment. Ce visualiseur dessine la recherche en direct pour que vous voyiez A* foncer droit vers le but pendant que Dijkstra s'étale dans toutes les directions.
Comment utiliser cette simulation
- Choisissez entre A*, Dijkstra et le parcours en largeur
- Dessinez des murs et placez le départ et l'arrivée
- Réglez la vitesse d'animation
Ce qu’il faut observer
- Dijkstra s'étend en cercle régulier ; A* s'étire vers le but
- Les deux trouvent un chemin de même longueur, mais A* examine bien moins de cases
- Des murs imposant un détour rendent le comportement des deux algorithmes beaucoup plus semblable
La physique derrière
L'algorithme de Dijkstra développe les nœuds par ordre de distance au départ, ce qui garantit le plus court chemin mais explore énormément de terrain inutile. A* ajoute une estimation heuristique de la distance restante, qui oriente la recherche vers le but. Pourvu que cette heuristique ne surestime jamais, A* garantit toujours le plus court chemin en visitant bien moins de nœuds.