Optimally fast shortest path algorithms for some classes of graphs

Abstract

Two algorithms for shortest path problems are presented. One is to find the all-pairs shortest paths (APSP) that runs in O(n ²logn + nm) time for n-vertex m-edge directed graphs consisting of strongly connected components with O(logn) edges among them. The other is to find the single-source shortest paths (SSSP) that runs in O(n) time for graphs reducible to the trivial graph by some simple transformations. These algorithms are optimally fast for some special classes of graphs in the sense that the former achieves O(n ²) which is a lower bound of the time necessary to find APSP, and that the latter achieves O(n) which is a lower bound of the time necessary to find SSSP. The latter can be used to find APSP, also achieving the running time O(n ²).

Keywords:

• Shortest path problem
• single-source shortest paths
• all-pairs shortest paths
• Dijkstra's algorithm
• Johnson's algorithm

C.R. Categories::

• G 2.2
• F 2.2