摘要
现有最短路径问题指的是狭义最短路径问题 ,针对该问题而设计的算法只能求得最短的一条路径 .前 N条最短路径拓宽了最短路径问题的内涵 (即不仅要求得最短路径 ,还要求得次短、再次短…第 N短路径 ) ,是广义最短路径问题 .在图论理论基础上分析问题之后 ,设计了一个递归调用 Dijkstra算法的新算法 ,该算法可以求取前 N条最短路径 ,而且时间、空间复杂度都为多项式阶 .该算法已经成功应用于一个交通咨询系统中 ,自然满足实时应用需要 .
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.
出处
《浙江大学学报（工学版）》
EI
CAS
CSCD
北大核心
2002年第5期531-534,共4页
Journal of Zhejiang University：Engineering Science
