Shortest path algorithms for nearly acyclic directed graphs

✍ Scribed by Tadao Takaoka

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 496 KB
• Volume: 203
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00292-2

✦ Synopsis

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.