Vi presenterar en approximation algoritm för alla par kortaste vägar (APSP) problem i vägde grafer. Vår algoritm löser APSP problem för viktade riktade grafer, med verkliga (positiva eller negativa) vikter, upp till ett additivt fel av. För varje par av hörn u, v, algoritmen finner en väg vars längd är som mest δ(u, v) +. Algoritmen är randomiserad och körs i Õ(n (-+3)/2 ) < O(n 2.688 ) tid, där n är antalet hörn och -är matris multiplikation exponenten. De absoluta vikterna får vara något beroende av att n är som mest n o(1) (vi noterar att även om vikterna är konstanter kan δ(u, v) vara linjär i n, medan felkravet är en liten konstant oberoende av n). Tydligt, -additiva approximationer generalisera exakta algoritmer för heltal viktade instanser. Därför är denna algoritm lika snabb som någon algoritm känd för heltal APSP i riktade grafer, och är mer allmän.
För ungefärlig APSP för verkliga värden grafer med vikter i [−n o (1),n o (1) ], Yuster REF presenterade en additiv ε- approximation i tid O (n +3 2 ).
Approximate shortest paths in weighted graphs
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}