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

• 作者: 张登荣 柴登峰
• 来源期刊: 浙江大学学报(工学版)
• 学科: 地球科学
• 关键词: 最短路径 N条最短路径 网络分析 地理信息系统 交通咨询系统
• 年，卷（期）: 2002,（5）
• 所属期刊栏目: 计算机技术、信息工程
• 页码范围: 531-534
• 页数: 4页
• 分类号: P208|O22
• 字数: 3795字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-973X.2002.05.013

摘要

现有最短路径问题指的是狭义最短路径问题,针对该问题而设计的算法只能求得最短的一条路径.前N条最短路径拓宽了最短路径问题的内涵(即不仅要求得最短路径,还要求得次短、再次短…第N短路径),是广义最短路径问题.在图论理论基础上分析问题之后,设计了一个递归调用Dijkstra算法的新算法,该算法可以求取前N条最短路径,而且时间、空间复杂度都为多项式阶.该算法已经成功应用于一个交通咨询系统中,自然满足实时应用需要.