An Algorithm of K Shortest Path Problem: Based on Bidirectional Searching
Song Gao, Feng Lu · 2007
Shortest path problem is always a hot topic in compute science, operational research and geographic information science. There are 5 main different types of this problem, one of them called k shortest path problem, which refers to this situation: not only the shortest path between two nods in a network should be calculated but also the second,third and even more shortest paths be calculated. The k shortest path algorithm based on directional searching is discussed in this paper, and it proposes a method to calculate out some considerable Paths for urban transportation networks. All of the considerable Paths calculated out are good paths in some sense, and there are many differences between each other, so it provides multi-choices of difference for users. And this kind of algorithm, which has a low time complexity, can often provide the shortest path which could be calculated by the dijkstra algorithm.