Vi anser att problemet med att beräkna alla par kortaste vägar (APSP) och kortaste vägar för k källor i en viktad graf i den distribuerade överbelastade modellen. För grafer med icke-negativa heltal kantvikter (inklusive nollvikter) bygger vi på en nyligen rörledningsalgoritm [1] för att erhålla aÕ(λ 1/4 · n 5/4 )-runda som är bundet till grafer med kantvikt som mest λ, och Õ(n ·  till 1/3 )-runda som är bundet till kortast vägavstånd som mest. Dessutom förenklar vi några av procedurerna i de tidigare APSP algoritmerna för icke-negativa kantvikter i [8, 2]. Vi presenterar också resultat för att beräkna h-hop kortaste vägar och kortaste vägar från k givna källor. I andra resultat presenterar vi en randomiserad exakt APSP algoritm för grafer med godtyckliga kantvikter som löper i Õ(n 4/3 ) rundor w.h.p. i n, vilket förbättrar det tidigare bästa Õ(n 3/2 ) bundet, vilket är deterministiskt. Vi presenterar också en Õ(n/ på 2 )-runda deterministisk (1 +  på) approximationsalgoritm för grafer med icke-negativa poly(n) heltalsvikter (inklusive noll kant-vikter), vilket förbättrar resultaten i [13, 11] som endast håller för positiva heltalsvikter.
I ett följepapper REF bygger vi på den piped algoritm som vi presenterar här för att få en algoritm för icke-negativa heltal kant-vikter (inklusive noll viktade kanter) som löper i Õ(n på 1/3 ) rundor där de kortaste stigavstånden är som mest och i Õ(n 5/4 λ 1/4 ) rundor när kantvikterna begränsas av λ.
New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}