文献类型：期刊文章

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

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

出　　处：《计算机工程与设计》

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

年　　份：2013

卷　　号：34

期　　号：11

起止页码：3900-3906

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA、CSA-PROQEUST、CSCD、CSCD_E2013_2014、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

摘　　要：为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。

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

分 类 号：TP301]