Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time - Brodnik, Andrej (Ars mathematica contemporanea, 2022)
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.
Keywords: all-pairs shortest paths; Floyd-Warshall algorithm; Floyd-Warshallov algoritem; najkrajše poti med vsemi pari vozlišč; probabilistic analysis; verjetnostna analiza