De distribuerade kortaste sökvägarna med en enda källa är ett av de mest grundläggande och centrala problemen i den distribuerade databehandlingen. Klassisk Bellman-Ford algoritm löser det i O (n) tid, där n är antalet hörn i inmatningsgrafen G. Peleg och Rubinovitj, FOCS'99, visade en lägre gräns för D + ❌ n för detta problem, där D är Hop-diameter av G. Huruvida detta problem kan lösas i o(n) tid när D är relativt liten är en stor ökänd öppen fråga. Trots intensiv forskning som gav nästan optimala algoritmer för den ungefärliga varianten av detta problem, inga framsteg rapporterades för det ursprungliga problemet. I detta dokument besvarar vi denna fråga på ett normativt sätt. Vi utformar en algoritm som kräver O ((n log n) 5/6 ) tid, för D = O ( n log n), och O (D 1/3 · (n log n) 2/3 ) tid, för större D. Denna körtid är sublinear i n i nästan hela intervallet av parametrar, specie cally, för D = o(n/ log 2 n). Vi generaliserar också vårt resultat i två riktningar. En är när kanterna har bandbredd b ≥ 1, och den andra är s-källor kortaste vägar problem. För båda problemen, vår algoritm ger gränser som förbättrar på den tidigare state-of-the-art i nästan hela utbudet av parametrar. I synnerhet tillhandahåller vi en alla-par kortaste banor algoritm som kräver O (n 5/3 · log 2/3 n) tid, även för b = 1, för alla värden av D. Vi utformar också rst algoritm med icke-trivial komplexitet garantier för att beräkna exakt kortaste banor i multipass semi-streaming modellen av beräkning. Ur teknisk synvinkel beräknar vår algoritm en Hopset G av ett skelett diagram G av G utan rst computing G själv. Vi genomför sedan en Bellman-Ford prospektering i G-G, samtidigt som vi beräknar de nödvändiga kanterna av G på y. Som ett resultat, vår algoritm beräknar exakt de kanter av G som det verkligen behöver, snarare än att beräkna ungefär hela G.
Problemet med att hitta en exakt lösning i sublinjär tid förblev öppet för år, och bara mycket nyligen Elkin REF gav en algoritm som kan lösa problemet i O(n log n)
Distributed exact shortest paths in sublinear time
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}