基于标号算法搜索过程的K最短路算法设计

发布时间：2022-10-19 11:14

　　K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的Dijkstra标号算法.该算法在搜索过程中得到一条最短路径的同时,获得了大量的临时标号信息;在此基础上,继续采用该算法利用这些临时标号信息进行标号,可以获得其他严密K最短路;将该算法与交叉口有延误的最短路径算法相结合,可方便的计算城市交通网络中交叉口有延误的K最短路径问题;该算法简化了K最短路的计算过程,提高了算法的计算效率.最后,利用一个简单网络介绍了该算法的计算过程. 

【文章页数】：7 页

【文章目录】：
1 KSP问题描述
2 限定无环KSP算法分析
    2.1 偏离路径算法
    2.2 改进Dijkstra算法
    2.3 智能算法
3 基于Dijkstra搜索过程的KSP算法
    3.1 Dijkstra搜索过程
    3.2 临时信息保留的Dijkstra算法
    3.3 K最短路径算法设计
4 计算过程分析
5 结论


【参考文献】：
期刊论文
[1]基于人工免疫的N最短路径检索算法[J]. 王峰,曼媛,王幸乐.  山东大学学报(理学版). 2017(09)
[2]基于矩阵运算K短路径算法[J]. 赵礼峰,黄奕雯.  计算机技术与发展. 2017(04)
[3]求解k最短路径问题的混合遗传算法[J]. 赵礼峰,于汶雨.  计算机技术与发展. 2016(10)
[4]突发事件条件下列车运行k-最短路模糊蚁群算法[J]. 张兰霞,秦勇,孟学雷,张涛.  模糊系统与数学. 2016(04)
[5]K最短路径算法与应用分析[J]. 付媛,朱礼军,韩红旗.  情报工程. 2015(01)
[6]K最短路径算法综述[J]. 徐涛,丁晓璐,李建伏.  计算机工程与设计. 2013(11)
[7]交通网络中路径求解遗传算法设计研究[J]. 杨信丰,李引珍.  兰州交通大学学报. 2010(04)
[8]关于k次短路径问题的分析与求解[J]. 白轶多,胡鹏,夏兰芳,郭峰林.  武汉大学学报(信息科学版). 2009(04)
[9]一种基于双向搜索的K则最优路径算法[J]. 高松,陆锋,段滢滢.  武汉大学学报(信息科学版). 2008(04)
[10]求解k条最优路径问题的遗传算法[J]. 马炫.  计算机工程与应用. 2006(12)



本文编号：3693263