Une preuve d'optimalité universelle pour l'algorithme de Dijkstra (en)

Une avancée en algorithmique : des chercheurs d’INSAIT démontrent qu’une modification élégante permet à l’algorithme de Dijkstra de devenir universellement optimal pour les plus courts chemins. Grâce à une nouvelle structure de tas (heap) qui exploite la localité des opérations, cet algorithme atteint des performances optimales au-delà du pire des cas pour tous les types de graphes. Une percée qui redéfinit les standards d’efficacité en algorithmique des graphes et offre une perspective inédite sur la performance des algorithmes séquentiels.