Approximate ripple spreading algorithm based on terminal strategy

Wang Ruixianga，Zhang Yingfeib，Li Hangʰ，Hu Xiaobingʰt （a.Sino-EuostoatonColfSfeceamp;in，iltonUesitf 300300，China）

Abstract： This paper proposed an improved algorithm to enhance the efficiency and adaptability of solving the k -shortest path problem （ k -SPP） incomplex network environments.The algorithm optimized the original ripple spreading algorithm（RSA） bylimiting thenumberofripplesgeneratedbyeachnode，which increasedcomputational eficiencyandformed theapproximate ripple spreading algorithm（ARSA）. It introduced a terminal strategy H_T ，by layering nodes and setting different ripple limits tobalanceoptimalityandcomputationaleficiency.Itfurtherenhanced thestrategy’sadaptabilitybyutilizingafuzzy inference system（FIS），which dynamically adjusted the H_T strategy based on network characteristics. Simulation experiments conducted on grid，random，small-world，and scale-free networks show that the H_T strategy significantly improves ARSA’s performance，while the FIS enables rapid configuration of the H_T strategy. Experimental results indicate that the proposed algorithm achieves high eficiency and reliability in solving k -SPP， providing a novel approach to path planning in complex network environments.

Key words： k -shortest paths problem； approximate ripple spreading algorithm；terminal strategy； fuzzy inference system;path planning

0 引言

k 最短路径问题（kshortestpathsproblem， k -SPP）是图论中的经典问题，其目标是在给定的有向图中寻找从起点到终点的k 条最短路径。在实际应用中， k -SPP被广泛应用于网络路由优化[1]、车辆巡检[2]、物流配送[3]及应急路线规划[4]等领域。例如，在网络路由中，k-SPP可用于计算多条备用路径，从而提升网络的可靠性和抗故障能力；在物流配送中，k-SPP则为规划提供了多条可选路径，增加了运输方案的灵活性。因此，如何高效地求解 k -SPP成为了学术研究的一个重要方向，众多学者提出了不同的解决方案[5-7]

大多数求解 k -SPP的算法基于1971年提出的Yen算法，采用了“偏离路径”的策略。在此方法中，每次计算第 k 条最短路径时，都会在第 k-1 条最优路径的基础上，将除了起点和终点之外的节点视为“偏离点”，从每个偏离点出发计算到终点的新的候选路径，并对这些候选路径进行排序，以确定第k条最短路径。这种方法虽然直观，但计算过程复杂，且效率较低，尤其是在处理大规模复杂图时更为明显。

为了降低Yen算法的求解 k -SPP的复杂度，研究人员提出了多种改进策略。文献[8]将“偏离路径”的计算过程视为动态更新网络中一对多的最短路径问题，每次搜索仅恢复一个节点和一个链路，从而重复利用先前搜索的最短路径结果。文献[9]采用反向一对多的Dijkstra算法预计算所有节点到目的地的最短路径，使用预先计算的子路径作为“偏离路径”。Chen等人[1°]在搜索\"偏离路径\"时，采用每次仅恢复一个节点的策略，并结合终身规划 A^* （lifeplanning A^* ， LPA^* ）算法来快速生成“偏离路径”。……