Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Cet article prouve que l'algorithme de Dijkstra pour trouver le plus court chemin est universellement optimal en termes de temps d'exécution et de comparaisons effectuées, lorsqu'il est associé à une structure de données de tas suffisamment efficace. Il introduit une nouvelle structure de tas qui garantit que les opérations sur le tas tirent parti de la localité, rendant l'extraction d'éléments récemment ajoutés moins coûteuse. Cela permet à Dijkstra de performer optimalement sur n'importe quelle topologie de graphe, car le nombre de comparaisons effectuées est lié à la structure du problème de parcours de distances, offrant une garantie de performance au-delà du cas worst-case.
