WSEAS Transactions on Information Science and Applications
Print ISSN: 1790-0832, E-ISSN: 2224-3402
Volume 12, 2015
An Iterative Algorithm for Single-Pair K Shortest Paths Computation
Authors: , ,
Abstract: In this paper, we report a novel method to compute the k shortest paths between a given pair of nodes in a given directed weighted graph, where loops are allowed in the solution paths. Once the shortest path from source node to goal node has been computed, the algorithm finds the next k - 1 shortest paths recursively. A* and on-the-fly search strategies are also applied to the proposed algorithm. The correctness of the presented algorithm is analyzed mathematically, and the simulative results confirming the superior performance of the algorithm to others in the literature for real road datasets are reported, especially when k is rather small.