K最短路径算法综述  

Review on K shortest paths algorithms

作　　者：徐涛[1,2] 丁晓璐[1,2] 李建伏[1] 

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300 [2]中国民航信息技术科研基地,天津300300

出　　处：《计算机工程与设计》2013年第11期3900-3906,3911,共8页Computer Engineering and Design

基　　金：天津市应用基础及前沿技术研究计划基金项目(09JCYBJC02300);中央高校基本科研业务费用中国民航大学专项B类基金项目(ZXH2011B003)

摘　　要：为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。To promote the applications of K shortest paths algorithm （KSP）, and to provide the relevant information for the further research on this algorithm, a review on the recent progress of KSP algorithms is given. According to restriction constrained on paths, the KSP problem can be classified into two types： the general KSP and the constrained loopless KSP. The basic ideas, research status and research progress for solving each type of two KSP problems are reviewed. Since KSP problem is very complex and the scale of the graph in application is very large, the efficiency has become an important indicator to evaluate a KSP algorithm. Time complexity is consequently a special concern in analyzing all kinds of KSP algorithms. Finally, future research directions of KSP are pointed out. The above work can give a valuable reference for multiple constraint shortest path problems.

关 键 词：KSP问题 路径限制条件 一般KSP问题 限定无环KSP问题 时间复杂度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]