Improved shortest path algorithms for nearly acyclic graphs

Abstract

Dijkstra's algorithm solves the single-source shortest path problem on any directed graph in O(m+nlogn) worst-case time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m is the number of edges in the graph. If the graph is nearly acyclic, then other algorithms can achieve a time complexity lower than that of Dijkstra's algorithm. Abuaiadh and Kingston gave a single source shortest path algorithm for nearly acyclic graphs with O(m + nlogt) worst-case time complexity, where the new parameter t is the number of delete-min operations performed in priority queue manipulation. For nearly acyclic graphs, the value of t is expected to be small, allowing the algorithm to outperform Dijkstra's algorithm. Takaoka, using a different definition for acyclicity, gave an algorithm with 0 ( m + n log k) worstcase time complexity. In this algorithm, the new parameter k is the maximum cardinality of the strongly connected components in the graph. This thesis presents several new shortest path algorithms that define trigger vertices, from which efficient computation of shortest paths through underlying acyclic structures in the graph is possible. Various definitions for trigger vertices are considered. One definition decomposes a graph into a unique set of acyclic structures, where each single trigger vertex dominates a single corresponding acyclic structure. This acyclic decomposition can be computed in O(m) time, thus allowing the single source problem to be solved in 0 ( m + r log r) worst-case time, where r is the resulting number of trigger vertices in the graph. For nearly acyclic graphs, the value of r is small and single-source can be solved in close to O(m) worst-case time. It is possible to define both monodirectional and bidirectional variants of this acyclic decomposition. This thesis also presents decompositions in which multiple trigger vertices dominate a single acyclic structure. The trigger vertices of such decompositions constitute feedback vertex sets. If trigger vertices are defined as a set of precomputed feedback vertices, then the all-pairs shortest path problem can be solved in O(mn + nr² ) worst-case time. This allows all-pairs to be solved in O(mn) worst-case time when a feedback vertex set smaller than the square root of the number of edges is known. For suitable graph types, these new algorithms offer an improvement on the time complexity of previous algorithms.