Algorithme de Dijkstra
Trouve le chemin le moins cher d’un départ à une arrivée. Il prend toujours l’endroit le moins cher en attente dans une file de priorité, si bien que les coûts se répandent depuis le départ comme une crue.
- temps O((V + E) log V)
- espace O(V)
- utilise une file de priorité
Que veulent dire ces termes ?
- Coût : ce que coûte un déplacement. Dans le labyrinthe, le sol coûte 1, la boue 3 et l’eau 9 ; dans le graphe, c’est le nombre sur l’arête.
- File de priorité : une file où passe d’abord le moins cher, pas le premier arrivé.
- Estimation (h) : une supposition du coût restant. A* ne reste exact que si elle n’est jamais trop haute.
- Relâcher une arête : vérifier si passer par l’endroit courant donne à un voisin un coût plus bas, et le prendre si c’est le cas.
- dans la file
- en cours
- traité
- chemin le moins cher
- sol · 1
- boue · 3
- eau · 9
- mur
Nouveau: Départ en A1 avec un coût de 0. C’est le seul élément de la file.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
Essayez : Choisissez le marais. Le chemin le moins cher fait tout le tour de la boue : deux fois plus de déplacements que la ligne droite, et pourtant moins cher (34 contre 36).
Comment ça marche
Chaque endroit reçoit un coût : 0 pour le départ, l’infini pour le reste. Dijkstra garde les endroits atteints dans une file de priorité et prend toujours le moins cher. Son coût est alors définitif, car tout autre chemin devrait passer par quelque chose d’au moins aussi cher. Il examine ensuite chaque voisin : si passer par l’endroit qu’il vient de prendre coûte moins que le coût actuel du voisin, le voisin prend ce nouveau coût et retient d’où il vient. Une fois l’arrivée prise, ces liens remontent le chemin le moins cher.
Quand le choisir
Dijkstra convient quand les déplacements coûtent des montants différents, jamais négatifs : cartes routières et GPS, routage réseau, correspondances aériennes les moins chères. Si tout déplacement coûte pareil, BFS donne la même réponse plus simplement. Avec des coûts négatifs, Dijkstra peut se tromper ; Bellman-Ford sait les gérer.