Låt G = (V, E) vara en oviktad oriktad graf på  och V = n vertex och  på m kanter. Låta δ(u, v) betecknar avståndet mellan hörn u, v  ska V. En algoritm sägs beräkna alla par t-ungefär kortaste vägar / avstånd, för några t ≥ 1, om för varje par hörn u, v  och V, den väg / avstånd som rapporteras av algoritmen är inte längre / större än t · δ (u, v). Denna uppsats presenterar två extremt enkla randomiserade algoritmer för att beräkna alla-par nästan 2-ungefärliga avstånd. Den första algoritmen kräver förväntad O(m 2/3 n log n + n 2 ) tid, och för någon u, v V rapporterar avståndet inte större än 2δ (u, v) + 1. Vår andra algoritm kräver förväntad O(n 2 log 3/2 n) tid, och för alla u, V V rapporterar avstånd begränsas av 2δ (u, v) + 3.
Baswana m.fl. I REF föreslås en randomiserad algoritm för beräkning av alla par nästan 2-ungefärliga avstånd med tids komplexitet av O(n 2 log 3/2 n).
All-Pairs Nearly 2-Approximate Shortest Paths in O ( n 2 polylog n ) Time ∗
{'venue': 'Electronic Colloquium on Computational Complexity (ECCC)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}