I den första delen av tidningen, vi granska alla-par kortaste vägar (APSP) problem och presentera en ny algoritm med körtid närmar sig O(n 3 / log 2 n), som förbättrar alla kända algoritmer för allmänna real-viktade täta grafer och är kanske nära det bästa resultatet möjligt utan att använda snabb matris multiplikation, Modulo några log n faktorer. I den andra delen av tidningen använder vi snabb matris multiplikation för att få verkligt subkubiska APSP algoritmer för en stor klass av "geometriskt viktade" grafer, där vikten av en kant är en funktion av koordinaterna för dess hörn. Till exempel, för grafer inbäddade i Euclidean utrymme av en konstant dimension d, får vi en tid bunden nära O(n 3−(3-)/(2d+4) ), där  på < 2.376; i två dimensioner, detta är O(n 2.922). Vårt ramverk utökar i hög grad det tidigare bedömda fallet av små-integer-viktade grafer, och ger för övrigt också det första verkligt subkubiska resultatet (nära O(n 3‐(3-)/4 ) = O(n 2.844 ) tid) för APSP i realvertex-viktade grafer, samt ett förbättrat resultat (nära O(n (3+-)/2 ) = O(n 2.688 ) tid) för alla-par lättast kortaste väg problem för små-integer-viktade grafer.
Många polylogaritmiska förbättringar följde, den sista var O(n 3 log 3 log n/ log 2 n) av Chan REF.
More algorithms for all-pairs shortest paths in weighted graphs
{'venue': "STOC '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}