文章基本信息

标题：Computational Efficiency of Optimized Shortest Path Algorithms.
本地全文：下载
作者：P. Biswas ; P. K. Mishra ; N. C. Mahanti 等
期刊名称：International Journal of Computer Science & Applications
印刷版ISSN：0972-9038
出版年度：2005
卷号：II
期号：II
出版社：Technomathematics Research Foundation
摘要：The main purpose of this study is to evaluate the computational efficiency of optimized shortest path algorithms. Our study establishes the relative order of the shortest path algorithms with respect to their known computational efficiencies is not significantly modified when the algorithms are adequately coded. An important contribution of this study is the inclusion of the re-distributive heap algorithm. In spite of having its best theoretical efficiency, the re-distributive heap algorithm does not emerge as the best method in terms of computational efficiency. The complexity of Dijkstra's algorithm depends heavily on the complexity of the priority queue Q. If this queue is implemented naively (i.e. it is re-ordered at every iteration to find the minimum node), the algorithm performs in O(n2), where n is the number of nodes in the graph. With a real priority queue kept ordered at all times, as we implemented it, the complexity averages O(n log m). The logarithm function stems from the collections class, a red-black tree implementation which performs in O(log (m)).