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

文档介绍：Advances in Applied Mathematics 应用数学进展, 2020, 9(8), 1313-1316
Published Online August 2020 in Hans.
*通讯作者。
文章引用: 白彩云, 李阳, 王越, 郭爽, 孙欣宇, 覃昶潔. 求解有向必经节点最短路径问题的算法[J]. 应用数学进展,
2020, 9(8): 1313-1316. DOI: .98154白彩云 等

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


Copyright © 2020 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY ).
/
Open Access


1. 引言
随着社会的进步和经济的蓬勃发展，人们通过网络进行货品交易的方式使得交通和物流规划成为一
个越来越受人关注的研究课题。最短路径的理论在交通和物流规划中有着广泛的应用。例如 Dijkstra 算
法，Flyod 等经典算法被人们沿用至今[1] [2] [3]。
现代的交通和物流问题往往不是单一的起点和终点的简单的路径规划问题。其中有一类问题叫做具
有必经节的路径规划问题[4] [5]。从起始点到终点的过程中，有多重路径可选，但是有一些节点是必须要
经过的节点。即可描述为如何寻找有必经节点的最短路径问题。该类问题的求解方式也较多，但是，在
有向图中，必经节点是有顺序的，一旦算出的最短路径中所含必经节点的顺序不符合现实要求，就需要
重新规划路径。若不存在符合有向图要求的最短路径，很多算法在发现这个结论前付出了太多的计算代
价。针对这一点，本文给出了另一种求解有向图