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. (C) 1998-Elsevier Science B.V. All rights reserved. [References: 9]
展开▼
