Algorithme de Dijkstra
Quel est le chemin le moins cher quand les déplacements ont des coûts différents ?
Développe toujours la case la moins chère à atteindre jusqu’ici, donc il trouve le chemin le moins cher même quand les pas coûtent des montants différents.
L’algorithme de Dijkstra note, pour chaque case, le coût le plus bas trouvé jusqu’ici pour l’atteindre, et garde la frontière dans une file de priorité ordonnée par ce coût. Il développe toujours la case la moins chère de la frontière.
Quand une case sort de la file, son coût est définitif : tout autre chemin vers elle passerait par une case de la frontière au moins aussi chère. Quand le but sort de la file, son chemin est le moins cher, pourvu qu’aucun coût ne soit négatif.
Sur une grille où un pas en diagonale coûte environ 1,41, c’est ce qui le distingue du parcours en largeur : il préfère le chemin le moins cher à celui qui a le moins de pas. Sans indice sur la position du but, il s’étale tout de même en disque autour du départ.
Chargement de la démo…
La grille avec Dijkstra sélectionné. Activez et désactivez les mouvements diagonaux et regardez le chemin le moins cher changer.
- 01Donner au départ un coût de 0 et aux autres cases l’infini ; mettre le départ dans une file de priorité.
- 02Prendre la case de coût le plus bas.
- 03Si c’est le but, remonter les parents mémorisés jusqu’au départ.
- 04Pour chaque voisine, calculer coût plus coût du pas. Si c’est plus bas que le coût enregistré de la voisine, l’enregistrer, mémoriser le parent et mettre la voisine en file.
- 05Répéter jusqu’à ce que la file soit vide.
function dijkstra(start, goal):
cost = {start: 0}
parent = {}
heap = [(0, start)]
while heap is not empty:
c, cell = heap.pop_min()
if c > cost[cell]: continue # an outdated entry
if cell == goal: return path_from(parent, goal)
for n, step in neighbours(cell):
new = c + step
if new < cost.get(n, infinity):
cost[n] = new
parent[n] = cell
heap.push((new, n))
return no_pathAvec un tas binaire comme file de priorité. Le facteur log est le prix du maintien de la frontière ordonnée.
- Chemin le moins cher, garanti, pour tout coût non négatif.
- N’a besoin d’aucune heuristique.
- Donne le coût le plus bas pour chaque case développée.
- S’étale dans toutes les directions, même loin du but.
- Plus lent que A* dès qu’une bonne heuristique est disponible.
- Échoue avec des coûts négatifs.
- 01Recherche de cheminLa référence du chemin le moins cher : A* avec une bonne heuristique doit trouver le même coût en développant moins de cases.