Algorithme de Dijkstra
L'algorithme de Dijkstra permet de rechercher le chemin de coût minimal entre un point de départ et une destination. Il est notamment utilisé dans des systèmes de navigation, des réseaux informatiques ou des jeux.
Ici, chaque case représente une zone à traverser. Certaines zones sont rapides, d'autres coûtent davantage, et les zones noires sont interdites.
Construisez un terrain, puis lancez l'algorithme.
| Cases explorées | Nombre de cases du chemin | Coût minimal |
|---|---|---|
| 0 | — | — |
Comment fonctionne l'algorithme ?
Au départ, la distance du point de départ vaut 0. Toutes les autres cases reçoivent une distance provisoire infinie.
L'algorithme choisit toujours la case non traitée ayant le coût cumulé le plus faible. Il examine ensuite ses voisines et calcule si le chemin passant par cette case améliore leur distance connue.
Lorsqu'une case a été traitée, son coût minimal est définitivement connu. L'algorithme continue jusqu'à atteindre la destination ou jusqu'à ce qu'il n'y ait plus de case accessible.
Le chemin jaune n'est pas forcément le plus court en nombre de cases : il est celui dont le coût total est le plus faible. Il peut donc préférer faire un détour pour éviter un terrain cher.
Essayez de placer une bande de terrain vert entre le départ et l'arrivée. Même si le trajet direct semble plus court, Dijkstra peut choisir un chemin plus long visuellement mais moins coûteux.