Algorithm and its application to N shortest paths problem
Chai Deng · Journal of Zhejiang University(Engineering Science) · 2002
As the shortest path denotes one path, algorithms designed for shortest path problem can get only one path. N shortest paths are N paths including the shortest one, the one inferior to the shortest one,eto. After reviewing the application of shortest poth problem,an N shortest paths problem was put forward and described. Graph theory was used to analyze the problem and results in four theoretical conclusions. Then, algorithm recursively calling the Dijkstra algorithm was designed and analyzed. Bath time conplexity and space conplexity are polynomial order.The algorithm was tested by experiment and applied to a traffic consultation system of Guangzhou City,it can meet the need of real time application.