基于节点压缩的寻径优化算法

廖志芳 陈亮名 彭志文 李严冰

(中南大学软件学院 湖南 长沙 410075)

基于节点压缩的寻径优化算法

廖志芳 陈亮名 彭志文 李严冰

(中南大学软件学院 湖南 长沙 410075)

最短路径问题是一个经典问题，而目前的研究大多是针对给定起点和终点，选择从起点到终点的最短路径，且取得了不少成果。而对于限定时间的最短路径问题的研究成果相对较少，这类问题在现实生活中却随处可见。针对这一问题提出几种限定时间的寻径优化算法，从对回溯法的改进到不同的节点压缩的方法，给出改进的回溯法以及三种基于节点压缩的寻径算法。算法实现在限定的时间内从起点出发经过给定的节点集合再到达终点的路径选择，并针对不同复杂度的网络图有相应合适的算法可以选择，从而有效地解决这类问题。

最短路径 限定时间 节点压缩 寻径

0 引 言

图论中单源最短路径问题[1-3]是一个经典问题，其在实际生活中应用广泛，如网络路由路径选择、车载导航、旅行路线等。解决这一问题的经典算法是Dijkstra EW.A于1959年提出的Dijkstra算法。但这一算法不能解决从起点开始必须经过指定的中间节点再到达终点的问题，然而这类问题实用性更强，比如：

(1) “邮递员问题”：邮递员从邮局出发为有信件的居民送完信件后回家，在给定的时间内为该邮递员选择一条行驶距离最短的路线；

(2) “旅行家问题”[4-6]：在指定的时间内为旅行者计算出一条旅行路线，从指定地点出发，到达指定旅游景点再到达指定目的地，要求路线的总行驶距离或者总行驶开销最短。……