前N条最短路径问题的算法及应用  

Algorithm and its application to N shortest paths problem

作　　者：柴登峰[1] 张登荣[1] 

机构地区：[1]浙江大学空间信息技术研究所,杭州浙江310027

出　　处：《浙江大学学报（工学版）》2002年第5期531-534,共4页Journal of Zhejiang University：Engineering Science

摘　　要：现有最短路径问题指的是狭义最短路径问题 ,针对该问题而设计的算法只能求得最短的一条路径 .前 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.

关 键 词：前N条最短路径问题 广义最短路径问题 网络分析 地理信息系统 交通咨询系统 图论 递归调用Dijkstra算法 

分 类 号：O157.6[理学—数学]