Shortest Path Algorithms for Nearly Acyclic Directed Graphs
Tadao Takaoka
Department of Computer Science
University of Canterbury
Abstract
Abuaiadh and Kingston gave an efficient algorithm for the single source shortest path problem for a nearly acyclic graph with O(m+n log t) computing time, where m and n are the numbers of edges and vertices of the given directed graph and t is the number of delete-min operations in the priority queue manipulation. They use the Fibonacci heap for the priority queue. If the graph is acyclic, we have t = 0 and the time complexity becomes O(m + n) which is linear and optimal. They claim that if the graph is nearly acyclic, t is expected to be small and the algorithm runs fast.
In the present paper, we take another definition of acyclicity. The degree of cyclicity cyc(G) of graph G is defined by the maximum cardinality of the strongly connected components of G. When cyc(G) =k, we give an algorithm for the single source problem with O(m + n log k) time complexity. Finally we give a hybrid algorithm that incorporates the merits of the above two algorithms.
Keywords: Algorithm, shortest paths, acyclic graph, nearly acyclic graph, priority queue, Fibonacci heap, Dijkstra's algorithm