Command Palette
Search for a command to run...
Briser la barrière de tri pour les plus courts chemins à origine unique dirigés
Briser la barrière de tri pour les plus courts chemins à origine unique dirigés
Ran Duan Jiayi Mao Xiao Mao Xinkai Shu Longhui Yin
Abstract
Nous proposons un algorithme déterministe en temps O(mlog2/3n) pour le problème des plus courts chemins à source unique (SSSP) sur les graphes orientés munis de poids d'arêtes réels et non négatifs, dans le modèle de comparaison-addition. Il s'agit du premier résultat à briser la borne de temps O(m+nlogn) de l'algorithme de Dijkstra sur les graphes creux, montrant ainsi que l'algorithme de Dijkstra n'est pas optimal pour le problème SSSP.