求解有向必经节点最短路径问题的算法

由天下分享时间：2025/1/11 11:56:52 加入收藏我要投稿点赞

Advances in Applied Mathematics 应用数学进展, 2024, 9(8), 1313-1316 Published Online August 2024 in Hans. http://www.hanspub.org/journal/aam https://doi.org/10.12677/aam.2024.98154

An Algorithm for Solving the Shortest Path Problem of Directed and Necessary Nodes

Caiyun Bai, Yang Li*, Yue Wang, Shuang Guo, Xinyu Sun, Changjie Qin

College of Science, Dalian Minzu University, Dalian Liaoning

stthth

Received: Aug. 1, 2024; accepted: Aug. 17, 2024; published: Aug. 24, 2024

Abstract

The shortest path problem with necessary nodes has a wide range of practical applications. How-ever, in the case of directed graph, many algorithms will have to perform a lot of repetitive calcu-lations because the order of the required nodes in the optimal path is not consistent with the real-ity. In this paper, an algorithm is proposed to solve the shortest path problem of required nodes in a directed graph, which can verify the existence of the shortest path conforming to the path order and solve the problem effectively.

Keywords

Necessary Nodes, Shortest Path, Dijkstra Algorithm

求解有向必经节点最短路径问题的算法

白彩云，李阳*，王越，郭爽，孙欣宇，覃昶潔

大连民族大学理学院，辽宁大连

收稿日期：2024年8月1日；录用日期：2024年8月17日；发布日期：2024年8月24日

摘要

具有必经节点的最短路径问题有着广泛的实际应用。但是在有向图的情况下，很多算法会因为所求最优路径中的必经节点顺序与实际不符而不得不进行大量重复性计算。本文针对这种情况提出了一种求解有向图必经节点最短路径问题的算法，可以更早检验是否存在符合路径顺序要求的最短路径并进行有效求解。

*通讯作者。

文章引用: 白彩云, 李阳, 王越, 郭爽, 孙欣宇, 覃昶潔. 求解有向必经节点最短路径问题的算法[J]. 应用数学进展, 2024, 9(8): 1313-1316. DOI: 10.12677/aam.2024.98154

白彩云等

关键词

必经节点，最短路径，Dijkstra算法

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0). http://creativecommons.org/licenses/by/4.0/

Open Access 1. 引言

随着社会的进步和经济的蓬勃发展，人们通过网络进行货品交易的方式使得交通和物流规划成为一个越来越受人关注的研究课题。最短路径的理论在交通和物流规划中有着广泛的应用。例如Dijkstra算法，Flyod等经典算法被人们沿用至今[1] [2] [3]。

现代的交通和物流问题往往不是单一的起点和终点的简单的路径规划问题。其中有一类问题叫做具有必经节的路径规划问题[4] [5]。从起始点到终点的过程中，有多重路径可选，但是有一些节点是必须要经过的节点。即可描述为如何寻找有必经节点的最短路径问题。该类问题的求解方式也较多，但是，在有向图中，必经节点是有顺序的，一旦算出的最短路径中所含必经节点的顺序不符合现实要求，就需要重新规划路径。若不存在符合有向图要求的最短路径，很多算法在发现这个结论前付出了太多的计算代价。针对这一点，本文给出了另一种求解有向图必经节点的方法，可以更早地检验是否存在符合有向图方向要求的必经节点路径。并用实例证实了方法的有效性。

2. 算法介绍

本文给出一种求解有向必经节点的最短路径问题的算法，利用合并节点的技术将问题简化。把求解最短路径的一个问题化为多个小问题来进行求解。成功回避了所求最短路径中不包含必经节点，或者必经节点的顺序不满足方向要求。这个算法还可以快速发现是否存在满足有向图的带有必经节点最短路径存在与否，避免计算代价。

算法步骤

第一步找到所有必经节点，按照已知的路径方向将必经节点排序，将集合记为X={x1,?,xn}，其中

xi,i=1,?,n是必经节点，下角标为经过节点的顺序；

第二步将直接连通(中间没有任何其他节点)的若干必经节点合并为一个点(即假设若xi和xj (i

第三步利用Dijkstra算法寻找每两个必经节点之间的最短路径，(即x1与x2之间，?，xi?1与xij之间，

xij与xj+1之间，?，xn?1与xn之间)及起点到x1的最短路径与xn到终点之间的最短路径；(若有任何两点之间不存在满足方向的连通路径，则不存在有向最短路径)；

第四步把所有最短路径链接起来就构成有向图的最短路径。

3. 一个有向必经节点最短路径问题

如图1所示，这是一个有向网络图。

假设起点为1，终点为11，而路径要求必须经过的节点为3，6，9。两个节点之间的数字代表路径长度。现在，我们要求解经过上述三个必经节点的最短路径。