Il s’agit d’une réalisation historique. Les informaticiens de l’Université de Tsinghua ont annoncé la percée la plus importante de l’efficacité algorithmique pour trouver la voie la plus courte des réseaux en plus de 40 ans. L’équipe a développé avec succès un nouvel algorithme qui surmonte la «barrière de tri» de longue date de l’algorithme de 1959 de Dijkstra, une pierre angulaire de l’informatique qui a tout propulsé, de la navigation GPS à la routage des données d’Internet. Cette évolution est sur le point d’avoir un impact transformateur sur une multitude d’industries, en particulier dans les domaines de la gestion et de la fabrication de la chaîne d’approvisionnement.
Pensez à une énorme carte de routes à sens unique (un graphique dirigé). Vous choisissez une ville de départ et voulez savoir jusqu’à quel point Toutes les autres villes sont de vous le long de la route la moins chère. Cette tâche «des chemins les plus courtes à source unique» alimente des choses comme la navigation, la logistique, le routage du réseau et l’IA du jeu.
Depuis des décennies, la solution incontournable Algorithme de Dijkstra. C’est merveilleusement fiable, mais cela passe beaucoup d’efforts aligner toutes les villes en augmentant la distance comme ça va. Cette «gamme complète» (tri) devient un puits de temps sur des réseaux géants et clairsemés.
La nouvelle recherche montre que vous pouvez obtenir toutes les distances sans aligner complètement les villes. Vous n’avez besoin que d’ordre suffisant pour continuer à avancer, non plus.
Expliquer tout cela
Expliquons maintenant un point de vue technique:
Le problème de chemin le plus court (SSSP) à source unique implique un graphique dirigé g = (v, e) avec n sommets et m bords, ainsi qu’un poids réel non négatif pour chaque bord (Duan et al. 2025, p. 1). L’objectif est de trouver la longueur du chemin le plus court d’un sommet source à tous les autres sommets V dans le graphique (Duan et al. 2025, p. 3). L’algorithme standard pour cette tâche est l’algorithme de Dijkstra, qui, lorsqu’il est implémenté avec des structures de données avancées comme Fibonacci ou des tas détendus, a une complexité temporelle de O (m + n log n) (Duan et al. 2025, p. 1). Cet algorithme fonctionne dans le modèle d’addition de comparaison, où seules les comparaisons et les ajouts de poids de bord sont autorisés, chaque opération prenant un temps d’unité (Duan et al. 2025, p. 1).
L’algorithme de Dijkstra fonctionne en extrayant à plusieurs reprises le sommet avec la distance minimale connue d’une file d’attente prioritaire et en relaxant ses bords sortants (Duan et al. 2025, p. 2). Un sous-produit de ce processus est qu’il trie les sommets par leur distance de la source (Duan et al. 2025, p. 1). Cet aspect de tri crée un goulot d’étranglement du temps, souvent appelé «barrière de tri», qui a été considéré comme une limite fondamentale pour les algorithmes SSSP, suggérant une limite inférieure de ω (n log n) (Duan et al. 2025, p. 2). Des travaux récents ont confirmé que si un algorithme doit sortir l’ordre trié des sommets par distance, l’algorithme de Dijkstra est optimal (Duan et al. 2025, p. 1). Cependant, la question restait de savoir si cette barrière pouvait être brisée pour les graphiques dirigés si seulement les distances elles-mêmes étaient nécessaires (Duan et al. 2025, p. 1). Les auteurs de la nouvelle étude présentent un algorithme déterministe qui y parvient, en cours d’exécution O (m log² / ³ n) Temps (Duan et al. 2025, p. 1). Ce résultat est le premier à briser le O (m + n log n) lié sur des graphiques clairsemés pour ce problème et est également le premier algorithme déterministe à le faire même pour les graphiques non dirigés (Duan et al. 2025, p. 2).
Le nouvel algorithme combine les principes de l’algorithme de Dijkstra et de l’algorithme Bellman-Ford (Duan et al. 2025, p. 2). L’algorithme Bellman-Ford détend tous les bords à plusieurs reprises et peut trouver des chemins les plus courts avec au plus k bords du temps O (Mk) sans avoir besoin de trier les sommets (Duan et al. 2025, p. 2). L’idée principale des chercheurs est de fusionner ces deux approches en utilisant une technique récursive, diviser et conquérir axée sur la réduction de la taille de la «frontière», qui est l’ensemble des sommets activement pris en compte par l’algorithme (Duan et al. 2025, p. 2).
Cadre algorithmique et hypothèses
L’algorithme fonctionne sous le modèle d’addition de comparaison (Duan et al. 2025, p. 3). Pour l’analyse, il est supposé que le graphique a un degré et un degré constants (Duan et al. 2025, p. 3). Les auteurs notent que tout graphique général peut être converti en cette forme par une transformation standard qui préserve les chemins les plus courts tout en créant un nouveau graphique avec des sommets et des bords O (m) (Duan et al. 2025, p. 3). L’algorithme maintient également une base de base d’estimation de distance[u] pour chaque sommet U, qui est toujours supérieur ou égal à la distance la plus courte D (U) (Duan et al. 2025, p. 3). Un sommet u est considéré comme «complet» si db[u] = D (U) (Duan et al. 2025, p. 3). Pour la simplicité de la présentation, le document suppose que tous les chemins ont des longueurs uniques, mais il fournit une méthode pour appliquer un ordre total sur les chemins en utilisant la comparaison lexicographique des tuples de la longueur du chemin, du nombre de sommets et de la séquence inverse des sommets, donc cette hypothèse ne limite pas la généralité de l’algorithme (Duan et al.2025, p. 4).
La procédure de chemin le plus court à plusieurs sources (BMSSP)
La composante principale de l’algorithme est une procédure récursive nommée un chemin le plus court multi-sources borné, ou BMSSP (Duan et al. 2025, p. 4). Cette procédure est conçue pour trouver toutes les vraies distances aux sommets inférieurs à une limite supérieure donnée B et dont les chemins les plus courts dépendent d’un ensemble de sommets «frontaliers» S (Duan et al. 2025, p. 4). L’algorithme est structuré comme un processus de division et de conquête avec des niveaux d’environ (log n) / t de récursion, où t: = ⌊log² / ³ (n) ⌋ est un paramètre (Duan et al. 2025, p. 4). Un appel à BMSSP (L, B, S) prend un niveau lle Bound B, et la frontière définit S comme entrée (Duan et al. 2025, p. 4). Il renvoie une nouvelle frontière, peut-être plus petite, B ′ ≤ B et un ensemble de sommets U qui sont maintenant terminés (Duan et al. 2025, p. 5). L’exécution peut être réussie, où B ′ = B, soit partiel, où B ′
Sous-routines clés
La procédure BMSSP repose sur deux composants clés pour atteindre son accélération (Duan et al. 2025, p. 5). Le premier est un sous-routine appelé Findpivots (Duan et al. 2025, p. 5). Cette fonction prend les ensembles de frontières et effectue une relaxation de type Bellman pour k étapes, où k: = ⌊log¹ / ³ (n) ⌋ (Duan et al. 2025, p. 4). Ce processus calcule les chemins les plus courts finaux pour les sommets dont les chemins de S sont courts (moins de k sommets) ou identifie un ensemble plus petit de «pivots» p ⊆ s (Duan et al. 2025, p. 5). Ces pivots sont des sommets dans S qui sont des racines de sous-arbres de chemin le plus court (contenant au moins k sommets), et le nombre de tels pivots est délimité par | ue | / k, où UE est l’ensemble des sommets d’intérêt (Duan et al. 2025, p. 6). Cela réduit efficacement la taille de la frontière qui doit être traitée dans les appels récursifs ultérieurs (Duan et al. 2025, p. 5).
Le deuxième composant est une structure de données spécialisée utilisée pour gérer les pivots et autres sommets sans les trier complètement (Duan et al. 2025, p. 6). Cette structure prend en charge trois opérations principales (Duan et al. 2025, pp. 6-7):
Insert: Ajoute une paire de valeurs de clé dans le temps amorti O (max {1, log (n / m)}), où n est le nombre d’éléments et m est un paramètre de taille de bloc (Duan et al. 2025, p. 6).BatchPrepend: Insère une liste de nouveaux éléments qui sont tous plus petits que tous les éléments existants, ce qui est efficace pour gérer les résultats des appels récursifs (Duan et al. 2025, p. 7).Pull: Extrait un bloc des plus petits éléments M de la structure sans trier toute la collection, ce qui fournit l’entrée pour l’appel récursif suivant de BMSSP (Duan et al. 2025, p. 7).
Cette structure de données est implémentée à l’aide d’une liste liée basée sur des blocs combinée à un arbre de recherche binaire auto-équilibré pour gérer les limites de bloc (Duan et al. 2025, p. 7). En combinant ces techniques, l’algorithme évite la nécessité de maintenir une file d’attente prioritaire entièrement triée de tous les n sommets (Duan et al. 2025, p. 2). Au lieu de cela, il répartit récursivement le problème, utilise des relaxations limitées de Bellman-Ford pour trouver des pivots et utilise une structure de données de tri partielle pour gérer efficacement l’ensemble beaucoup plus petit de pivots pour la prochaine étape de la récursivité (Duan et al. 2025, p. 5). La complexité du temps totale est dérivée des travaux effectués à chacun des niveaux de récursivité O ((log n) / t), ce qui conduit à la limite finale O (m log² / ³ n) (Duan et al. 2025, p. 14).
