Evaluation of algorithms for finding shortest paths in a network
Dani Zugan · 2023
The paper evaluates three different algorithms for computing allpairs shortest paths.We compare the well-known Floyd-Warshall algorithm with two simple modifications of it.The key difference lies in the fact that the relaxations are done in a smarter way.We evaluate the algorithms on three different graph models -uniform Erdős-Rényi, binomial Erdős-Rényi, and Albert-Barabási.Based on the results, we can observe that both modified algorithms outperform the Floyd-Warshall algorithm.