A Kth Shortest Path Algorithm Implemented with Bi-directional Search

A new Kth shortest path algorithm based on bidirectional search is set forward in this paper.Based on the classical Dijkstra's shortest path algorithm,the presented algorithm conducts the path searching both from the source and destination nodes at the same time,and constructs the shortest path trees in positive and reverse sequence alternately so to populate several reasonable shortest paths between the start and destination nodes.The principle and implementation of the algorithm is described in detail and time complexity is analyzed.The efficiency and accuracy are verified with a real road network.