Efficient algorithms for solving shortest paths on nearly acyclic directed graphs

摘要

This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G = (V, E). The new algorithms improve on the worst-case running time of previous algorithms. Such algorithms use the concept of a 1-dominator set. A 1-dominator set divides the graph into a unique collection of acyclic subgraphs, where each acyclic subgraph is dominated by a single associated trigger vertex. The previous time for computing a 1-dominator set is improved from O(mn) to O(m), where m = |E| and n = |V|. Efficient shortest path algorithms only spend delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. Under this framework, the time complexity for the all-pairs shortest path (APSP) problem is improved from O(mn + nr log r) to O(mn + r² log r), where r is the number of triggers. Here the second term in the complexity results from delete-min operations in a heap of size r. The time complexity of the APSP problem on the broader class of nearly acyclic graphs, where trigger vertices correspond to any precomputed feedback vertex set, is similarly improved from O(mn + nr²) to O(mn + r³). This paper also mentions that the 1-dominator set concept can be generalised to define a bidirectional 1-dominator set and k-dominator sets.