2012/12/27 by Andrej Brodnik, Brodnik, Andrej, Marko Grgurovič +1
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1212.6327
Given an arbitrary, non-negatively weighted, directed graph G=(V,E) we present an algorithm that computes all pairs shortest paths in time O(m^* n + m \lg n + nTψ(m^*, n)), where m^* is the number of different edges contained in shortest paths and Tψ(m^*, n) is a running time of an algorithm to solve a single-source shortest path problem (SSSP). This is a substantial improvement over a trivial n times application of ψ that runs in O(nTψ(m,n)). In our algorithm we use ψ as a black box and hence any improvement on ψ results also in improvement of our algorithm. Furthermore, a combination of our method, Johnson's reweighting technique and topological sorting results in an O(m^*n + m \lg n) all-pairs shortest path algorithm for arbitrarily-weighted directed acyclic graphs. In addition, we also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP.