Geodesic
Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
Ars Mathematica Contemporanea, Tome 22 (2022) no. 1, article no. 01, 22 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

The paper describes two relatively simple modifications of the well-known Floyd-Warshall algorithm for computing all-pairs shortest paths. A fundamental difference of both modifications in comparison to the Floyd-Warshall algorithm is that the relaxation is done in a smart way. We show that the expected-case time complexity of both algorithms is O(n2log2n) for the class of complete directed graphs on n vertices with arc weights selected independently at random from the uniform distribution on [0, 1]. Theoretically best known algorithms for this class of graphs are all based on Dijkstra’s algorithm and obtain a better expected-case bound. However, by conducting an empirical evaluation we prove that our algorithms are at least competitive in practice with best know algorithms and, moreover, outperform most of them. The reason for the practical efficiency of the presented algorithms is the absence of use of priority queue.
DOI : 10.26493/1855-3974.2467.497
Keywords: All-pairs shortest paths, probabilistic analysis 
@article{10_26493_1855_3974_2467_497,
     author = {Andrej Brodnik and Marko Grgurovi\v{c} and Rok Po\v{z}ar},
     title = {Modifications of the {Floyd-Warshall} algorithm with nearly quadratic expected-time},
     journal = {Ars Mathematica Contemporanea},
     eid = {01},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2022},
     doi = {10.26493/1855-3974.2467.497},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2467.497/}
}
TY  - JOUR
AU  - Andrej Brodnik
AU  - Marko Grgurovič
AU  - Rok Požar
TI  - Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
JO  - Ars Mathematica Contemporanea
PY  - 2022
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2467.497/
DO  - 10.26493/1855-3974.2467.497
LA  - en
ID  - 10_26493_1855_3974_2467_497
ER  - 
%0 Journal Article
%A Andrej Brodnik
%A Marko Grgurovič
%A Rok Požar
%T Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
%J Ars Mathematica Contemporanea
%D 2022
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2467.497/
%R 10.26493/1855-3974.2467.497
%G en
%F 10_26493_1855_3974_2467_497
Andrej Brodnik; Marko Grgurovič; Rok Požar. Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time. Ars Mathematica Contemporanea, Tome 22 (2022) no. 1, article  no. 01, 22 p. doi : 10.26493/1855-3974.2467.497. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2467.497/

Cité par Sources :