一种基于SPFA算法的城市K则最短路径获取方法

摘要

本发明公开了一种基于SPFA算法的城市K则最短路径获取方法，包括：1.获取实时城市道路路网图；2.为每个交叉口节点初始化可变列表标签；3.通过Qkt中的交叉口节点完成第k短路径的前向更新，并进行可变列表标签中的插入排序；4.对无后续作用的交叉口节点进行适当剪枝；5.找到从起点交叉口节点vs至终点交叉口节点ve的若干条距离值及最短路径，并回溯和输出。本发明能根据当前时刻终点交叉口节点ve的距离值对其余交叉口节点进行剪枝操作来缩小有效更新范围，避免冗余计算，并充分利用最短路算法松弛过程中的信息求解K则最短路径，从而满足多路径导航选择的现实需求。