Dit is een mijlpaalprestatie. Computerwetenschappers van de Tsinghua University hebben de belangrijkste doorbraak aangekondigd in algoritmische efficiëntie voor het vinden van het kortste pad in netwerken in meer dan 40 jaar. Het team heeft met succes een nieuw algoritme ontwikkeld dat de al lang bestaande “sorteerbarrière” van Dijkstra’s gerenommeerde algoritme uit 1959 overwint, een hoeksteen van computergebruik die alles heeft aangedreven, van GPS-navigatie tot de gegevensrouting van internet. Deze ontwikkeling is klaar om een transformerende impact te hebben op een veelheid van industrieën, met name op het gebied van supply chain management en productie.
Denk aan een enorme kaart van eenrichtingswegen (een gerichte grafiek). Je kiest een startende stad en wilt het weten Hoe ver Elke andere stad is van jou langs de goedkoopste route. Deze “single-source kortste paden” -taak voedt dingen zoals navigatie, logistiek, netwerkroutering en game AI.
Al tientallen jaren is de go-to-oplossing Dijkstra’s algoritme. Het is prachtig betrouwbaar, maar het levert veel moeite Alle steden op een rij staan door afstand te nemen Zoals het gaat. Dat “volledige line-up” (sorteren) een tijdzink wordt op gigantische, schaarse netwerken.
Het nieuwe onderzoek toont aan dat u alle afstanden kunt krijgen zonder de steden volledig in de rij te zetten. Je hebt alleen voldoende bestelling nodig om vooruit te blijven – geen meer.
Het uitleggen allemaal
Laten we het nu uitleggen vanuit een technisch oogpunt:
Het probleem met de kortste pad (SSSP) met één bron omvat een gerichte grafiek g = (v, e) met N hoekpunten en M Randen, samen met een niet-negatief echt gewicht voor elke rand (Duan et al. 2025, p. 1). Het doel is om de lengte van het kortste pad te vinden van een bronstekst naar elke andere hoekpunt V in de grafiek (Duan et al. 2025, p. 3). Het standaardalgoritme voor deze taak is het algoritme van Dijkstra, dat, wanneer geïmplementeerd met geavanceerde gegevensstructuren zoals Fibonacci of ontspannen hopen, een tijdcomplexiteit heeft van O (M + N Log N) (Duan et al. 2025, p. 1). Dit algoritme werkt in het vergelijking-addition-model, waar alleen vergelijkingen en toevoegingen van randgewichten zijn toegestaan, waarbij elke bewerking eenheidstijd neemt (Duan et al. 2025, p. 1).
Dijkstra’s algoritme werkt door het hoekpunt herhaaldelijk te extraheren met de minimaal bekende afstand van een prioriteitswachtrij en de uitgaande randen te ontspannen (Duan et al. 2025, p. 2). Een bijproduct van dit proces is dat het hoekpunten sorteert op afstand tot de bron (Duan et al. 2025, p. 1). Dit sorteeraspect creëert een tijdknelpunt, vaak de ‘sorteerbarrière’ genoemd, waarvan wordt beschouwd dat het een fundamentele limiet is voor SSSP -algoritmen, wat een ondergrens van ω (n log n) suggereert (Duan et al. 2025, p. 2). Recent werk bevestigde dat als een algoritme de gesorteerde volgorde van hoekpunten op afstand moet uitvoeren, het algoritme van Dijkstra optimaal is (Duan et al. 2025, p. 1). De vraag bleef echter of deze barrière kon worden verbroken voor gerichte grafieken als alleen de afstanden zelf nodig waren (Duan et al. 2025, p. 1). De auteurs van de nieuwe studie presenteren een deterministisch algoritme dat dit bereikt, die binnenkomt O (m log²/³ n) Tijd (Duan et al. 2025, p. 1). Dit resultaat is de eerste die de O (m + n log n) verbreekt op schaarse grafieken voor dit probleem en is ook het eerste deterministische algoritme dat dit zelfs voor niet -gerichte grafieken doet (Duan et al. 2025, p. 2).
Het nieuwe algoritme combineert principes van zowel Dijkstra’s algoritme als het Bellman-Ford-algoritme (Duan et al. 2025, p. 2). Het Bellman-Ford-algoritme ontspant alle randen meerdere keren en kan de kortste paden vinden met de meeste K-randen in O (Mk) tijd zonder dat ze hoekpunten moeten sorteren (Duan et al. 2025, p. 2). Het kernidee van de onderzoekers is om deze twee benaderingen samen te voegen met behulp van een recursieve, verdeel- en veroveringstechniek gericht op het verminderen van de grootte van de ‘grens’, wat de set hoekpunten is die actief door het algoritme worden overwogen (Duan et al. 2025, p. 2).
Algoritmisch raamwerk en veronderstellingen
Het algoritme werkt onder het vergelijking-addition-model (Duan et al. 2025, p. 3). Voor de analyse wordt aangenomen dat de grafiek een constante in-degree en out-graad heeft (Duan et al. 2025, p. 3). De auteurs merken op dat elke algemene grafiek naar deze vorm kan worden omgezet door een standaardtransformatie die de kortste paden bewaart en tegelijkertijd een nieuwe grafiek met O (m) hoekpunten en randen maakt (Duan et al. 2025, p. 3). Het algoritme handhaaft ook een afstandsraming DB[u] Voor elke hoekpunt U, die altijd groter is dan of gelijk is aan de ware kortste afstand D (U) (Duan et al. 2025, p. 3). Een hoekpunt u wordt beschouwd als “compleet” als DB[u] = D (U) (Duan et al. 2025, p. 3). Voor de eenvoud van de presentatie veronderstelt het papier dat alle paden unieke lengtes hebben, maar het biedt een methode om een totale volgorde op paden af te dwingen met lexicografische vergelijking van tupels van padlengte, hoekpunttelling en de omgekeerde reeks van hoekpunten, dus deze veronderstelling beperkt het algoritme -generaliteit (Duan et al. 2025, p. 4).
De procedure met begrensde multi-source kortste pad (BMSSP)
Het hoofdcomponent van het algoritme is een recursieve procedure met de naam begrensde multi-source kortste pad of BMSSP (Duan et al. 2025, p. 4). Deze procedure is ontworpen om alle echte afstanden te vinden op hoekpunten die minder zijn dan een gegeven bovengrens B en wiens kortste paden afhankelijk zijn van een set “frontier” hoekpunten S (Duan et al. 2025, p. 4). Het algoritme is gestructureerd als een verdeel- en veroveringsproces met ongeveer (log n)/t recursieniveaus, waar t: = ⌊log²/³ (n) ⌋ is een parameter (Duan et al. 2025, p. 4). Een oproep naar BMSSP (L, B, S) neemt een niveau lThe Bound B en de Frontier Set S als invoer (Duan et al. 2025, p. 4). Het retourneert een nieuwe, mogelijk kleinere, grens B ′ ≤ B en een set hoekpunten U die nu voltooid zijn (Duan et al. 2025, p. 5). De uitvoering kan succesvol zijn, waarbij b ′ = b, of gedeeltelijk, waarbij b ′
Belangrijke sub-routines
De BMSSP -procedure is gebaseerd op twee belangrijke componenten om zijn versnelling te bereiken (Duan et al. 2025, p. 5). De eerste is een subroutine genaamd FindPivots (Duan et al. 2025, p. 5). Deze functie neemt de Frontier-set S en voert een Bellman-Ford-achtige ontspanning uit voor k Stappen, waar K: = ⌊log¹/³ (n) ⌋ (Duan et al. 2025, p. 4). Dit proces berekent ofwel de uiteindelijke kortste paden voor hoekpunten waarvan de paden van S kort zijn (minder dan k hoekpunten) of identificeert een kleinere set “pivots” p ⊆ s (Duan et al. 2025, p. 5). Deze pivots zijn hoekpunten in S die wortels zijn van grotere kortste-path-substrees (die ten minste K hoekpunten bevatten), en het aantal van dergelijke pivots wordt begrensd door | ue |/k, waarbij UE de set van interessante hoekpunten is (Duan et al. 2025, p. 6). Dit vermindert effectief de grootte van de grens die moet worden verwerkt in volgende recursieve oproepen (Duan et al. 2025, p. 5).
De tweede component is een gespecialiseerde gegevensstructuur die wordt gebruikt om de pivots en andere hoekpunten te beheren zonder ze volledig te sorteren (Duan et al. 2025, p. 6). Deze structuur ondersteunt drie hoofdactiviteiten (Duan et al. 2025, pp. 6-7):
Insert: Voegt een sleutelwaardepaar toe in afgeschreven O (max {1, log (n/m)})) tijd, waarbij n het aantal items is en m een blokgrootteparameter is (Duan et al. 2025, p. 6).BatchPrepend: Voegt een lijst in met nieuwe items die allemaal kleiner zijn dan alle bestaande items, die efficiënt zijn voor het verwerken van resultaten van recursieve oproepen (Duan et al. 2025, p. 7).Pull: Extraheert een blok van de kleinste M -items uit de structuur zonder de hele collectie te sorteren, die de invoer biedt voor de volgende recursieve oproep van BMSSP (Duan et al. 2025, p. 7).
Deze gegevensstructuur wordt geïmplementeerd met behulp van een op blokken gebaseerde gekoppelde lijst gecombineerd met een zelfveranderende binaire zoekboom om blokgrenzen te beheren (Duan et al. 2025, p. 7). Door deze technieken te combineren, vermijdt het algoritme de noodzaak om een volledig gesorteerde prioriteitswachtrij van alle N hoekpunten te handhaven (Duan et al. 2025, p. 2). In plaats daarvan wordt het probleem recursief verdeeld, gebruikt het beperkte Bellman-Ford-relaxaties om pivots te vinden en gebruikt het een gedeeltelijke sorteergegevensstructuur om de veel kleinere set pivots voor de volgende fase van de recursie efficiënt te beheren (Duan et al. 2025, p. 5). De totale tijdcomplexiteit is afgeleid van het werk dat wordt uitgevoerd bij elk van de O ((log n)/t) niveaus van recursie, wat leidt tot de laatste o (m log²/³ n) gebonden (Duan et al. 2025, p. 14).
