首页 | 本学科首页   官方微博 | 高级检索  
     

前N条最短路径问题的算法及应用
引用本文:柴登峰,张登荣.前N条最短路径问题的算法及应用[J].浙江大学学报(自然科学版 ),2002,36(5):531-534.
作者姓名:柴登峰  张登荣
作者单位:浙江大学空间信息技术研究所 杭州浙江310027 (柴登峰),浙江大学空间信息技术研究所 杭州浙江310027(张登荣)
摘    要:现有最短路径问题指的是狭义最短路径问题,针对该问题而设计的算法只能求得最短的一条路径。前N条最短路径拓宽了最短路径问题的内涵(即不仅要求得最短路径,还要求得次短、再次短…第N短路径),是广义最短路径问题,在图论理论基础上分析问题之后,设计了一个递归调用Dijkstra算法的新算法,该算法可以求取前N条最短路径,而且时间、空间复杂度都为多项式阶。该算法已经成功应用于一个交通咨询系统中,自然满足实时应用需要。

关 键 词:前N条最短路径问题  广义最短路径问题  网络分析  地理信息系统  交通咨询系统  图论  递归调用Dijkstra算法
文章编号:1008-973X(2002)05-0531-04
修稿时间:2001年10月24

Algorithm and its application to N shortest paths problem
CHAI Deng feng,ZHANG Deng rong.Algorithm and its application to N shortest paths problem[J].Journal of Zhejiang University(Engineering Science),2002,36(5):531-534.
Authors:CHAI Deng feng  ZHANG Deng rong
Abstract: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.
Keywords:shortest path  N  shortest paths  network analysis  traffic consultation system  GIS
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号