Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time

angleški

2022

letnik 22, številka 1

all-pairs shortest paths   Floyd-Warshall algorithm   Floyd-Warshallov algoritem   najkrajše poti med vsemi pari vozlišč   probabilistic analysis   verjetnostna analiza

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

V članku sta opisani dve relativno preprosti spremembi dobro znanega Floyd-Warshallovega algoritma za izračun najkrajših poti med vsemi pari vozlišč. Bistvena razlika obeh sprememb v primerjavi s Floyd-Warshallovim algoritmom je v tem, da se sproščanje izvede na pameten način. Pokažemo, da je pričakovana časovna zahtevnost obeh algoritmov ?$O(n^2\log^2 n)$? za razred polnih usmerjenih grafov na ?$n$? vozliščih, pri čemer so uteži na povezavah izbrane neodvisno z vrednostmi enakomerno porazdeljene naključne spremenljivke na intervalu ?$0,1$? Teoretično najboljši algoritmi za ta razred grafov temeljijo na Dijkstrovem algoritmu in dosežejo boljšo mejo v pričakovanem primeru. Kljub temu z empiričnim ovrednotenjem pokažemo, da sta naša algoritma v praksi vsaj konkurenčna z najbolj znanimi algoritmi in poleg tega prekašata večino od njih. Razlog za praktično učinkovitost predstavljenih algoritmov je odsotnost uporabe vrste s prednostjo.

22.11.2022