K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths
K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths
复制标题
K*：一种用于查找 k 最短路径的定向即时算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
S. Leue
中科院分区：
文献类型：
--
作者：
Husain Aljazzar;S. Leue
本文提出了一个新的算法，称为K ′，用于在给定的有向赋权图中寻找指定顶点对之间的k条最短路。与求解该问题的最著名的算法Eppstein算法相比，K算法有两个优点.首先，K是动态执行的，这意味着它不需要图显式可用并存储在主存中。将根据需要生成图形的部分。其次，K是一个有向算法，它允许使用启发式函数来指导搜索。这导致了显着的改善，在内存和运行时的要求，许多实际的问题实例。我们证明了K的正确性，并证明了它保持了O（m+ knlog（kn））的最坏情况运行时复杂度和O（kn + m）的空间复杂度，其中n是图的顶点数，m是图的边数.我们提供的实验结果，说明了该算法的可扩展性。
We present a new algorithm, called K � , for finding the k shortest paths between a designated pair of ver- tices in a given directed weighted graph. Compared to Eppstein's algorithm, which is the most prominent algorithm for solving this problem, Khas two advan- tages. First, Kperforms on-the-fly, which means that it does not require the graph to be explicitly available and stored in main memory. Portions of the graph will be generated as needed. Second, Kis a directed al- gorithm which enables the use of heuristic functions to guide the search. This leads to significant improve- ments in the memory and runtime demands for many practical problem instances. We prove the correctness of Kand show that it maintains a worst-case runtime complexity of O(m+k n log(k n)) and a space complex- ity of O(k n + m), where n is the number of vertices and m is the number of edges of the graph. We provide experimental results which illustrate the scalability of the algorithm.