最短路径算法——Dijkstra算法

最短路径算法——Dijkstra算法

苟中涛

重庆交通大学 交通运输学院 重庆 400074

摘要：数据结构作为计算机科学的核心，已经成为人们必须掌握的一切信息知识。作为经典的最短路径算法，Dijkstra算法数据结构被在生活中的各方面都有所体现。本文从数据结构和最短路径算法的定义入手，介绍了Dijkstra算法的算法优缺点和算法实例，最后阐述了最短路径算法在现实生活中的作用，说明该算法的重要意义。

关键词：最短路径；Dijkstra算法；应用

一、数据结构与算法

1.1 数据结构

数据结构是解释数据之间关系的科学。典型的数据结构包括数组、链表、树和图[1]。如何准确地使用各种数据结构至关重要。这种数据结构就是图表，它是“树型”数据结构的扩展。节点是一个节点（单独的节点），不能连接或连接到另一个节点。结果，图中节点之间的关系变得更加复杂，并且通过计算机从一个节点到另一个节点的路径变得更加困难。

数据结构彼此具有一个或多个某种联系的元素数据汇总。一般情况下，经过筛选的数据结构可以让用户感受到良好的体验或使用效率。数据逻辑结构、数据存储结构和数据操作三部分是数据结构研究的主要内容。线性结构和非线性结构一起组成了数据结构中的逻辑结构。对线性结构的解释是：简单的一个表就是一种线性结构，这个表中所有的节点都符合线性关系。除此之外，线性表是一种典型的线性结构，栈、队列、字符串都是线性结构。对非线性结构的解释是：在一个简单表中的节点之间存在若干个对应关系是非线性结构。在现实应用中，非线性结构主要包括了数组、树结构、图结构等数据结构。

1.2最短路径算法

最短路径在图论中定义为在有向图中两结点间找一条权值最小的路径。最短路径算法是对图状结构进行分析，找到需要的、合适的结点及路径，在交通、路径规划、城市建设、灾难逃生等领域广泛应用[2]。

最短路径法是一种机器学习技术，用于搜索连通图中结点之间的最短路径，是计算复杂系统中发现最优路径的有效方法。最短路径法可以应用于许多不同类型的问题，包括路由算法、资源分配问题、最优布线、交通规划等，还可以被用于搜索引擎中搜索优化的相关工作。

对解决办法的精准和确定的描述称之为算法，它是以一连串清楚的命令来处理相应的问题。算法是某种策略的集中体现，通常以完整的方式阐述问题。换句话说，对于某些规定的输入要求，自然可以在相应的时间内获取所需要的输出。若算法自身有问题或者和某个问题不是对应关系，那么就不能用这个算法来解决问题。当然，每个不同的算法对应着不同的时间复杂度和空间复杂度，因此，时间复杂度和空间复杂度也成了衡量一个算法好坏的标准。

二、Dijkstra算法

2.1Dijkstra算法思路

EdsgerW.Dijkstra提出了Dijkstra算法。这个算法的大致流程就是第一步先算出权值最小的一条最短距离，第二步按照上一步的办法算出权值第二小的一条最短距离，第三步就是重复第一步和第二步的步骤，一直到初始出发点到其他剩余的全部顶点的最短距离全部得出为止。Dijkstra算法步骤一共分为三步：

第一步：最初，顶点集s只包含源点v，即s={v}，顶点v到自身的距离为0。顶点集U=V-S包含除v以外的顶点，并且在u中从源点v到顶点i的距离是边（弧）上的权重（如果v和i有边〈v，i〉）或（如果顶点i不是v的邻居）。第二步：从u中选择一个顶点u，该顶点u是从源点v到u的最小距离，并将顶点u添加到s中（所选距离是从源点v到顶点u的最短路径长度）。第3步：使用顶点u作为新考虑的中间点，修改从源点v到u中每个顶点j（jU）的距离。重复步骤2和3，直到s包含所有顶点，即u为空。

2.2 Dijkstra算法实现

首先，设置距离数组dist[o.. n-1]，dist[i]用于保存从源点v到顶点i的当前最短路径长度。其次，path[j]保存从源点到顶点j的最短路径，该顶点j实际上是最短路径上的前一个顶点u，即：path[j]=u.最后，当找到最短路径时，从path [j]向前外推从源点到顶点j的最短路径。

2.3 Dijkstra算法实例

下图是一个包含了四个节点的图，权值在图上已经标注出，求1节点到其他节点的最短路径。

图2-1简单有向图

求1节点到其他节点的最短路径，算法过程见下表：

表2-1Dijkstra算法实现过程

由上表第4行可以知道，从1节点到其他节点的最短路径分别为：1节点→2节点：1→3→2，权值为10,1节点→3节点：1→3，权值为3，1节点→4节点：1→3→4，权值为4.

三、Dijkstra算法的应用

3.1在物流运输中的应用

最短路径算法可以应用于生活的许多地方，但往往被忽视，网购在生活中流行起来之后。物流和运输也随之发生，但对于车辆、飞机、船只等选择最短的距离、成本最低或时间最短成为运输过程中的一个问题，相关部门非常重视。比如物流运输车辆在运送货物时，如果仅仅考虑起点和终点之间的距离最短，那肯定忽略了时间因素以及成本因素对路径选择的影响。通常物流运输会把时间和距离或者把费用成本和距离综合一起考量，从而选择一条最短路径。因此使用最短路径算法并根据实际情况进行改进，可以为相关公司和政府机构提供最有效的路径选择，其经济效益相当可观。

3.2在日常出行中的应用

最短路径算法在不断影响我们的生活。GPS成为智能手机和车辆的基本功能，也用于使用地图和汽车导航来确定最佳路线。最短路径算法在我们日常出行中为我们提供了强有力的支撑，比如用户在使用谷歌在线地图来规划一条线路时，它通常会提供距离最短、时间最少、费用最省的三条路线，供用户选择。在物流选址方面，若某个公司要建立一个物流配送中心，那么肯定会考虑物流配送中心到城市各个地方的距离，这里考虑的就是物流配送中心到城市各个地方的最短距离，以此来确定物流配送中心的最佳选址位置。除此之外，最短路径算法在应急救援，网络分析等各方面都有应用。

参考文献

[1]梁晓辉,慕永辉,吴北华,江宇.关于路径规划的相关算法综述[J].价值工程,2020,39(03):295-299.

[2]贺喜玲,季焕淑.最短路径算法[J].大科技·科技天地,2021(6).

[3]赵磊，侯莉莉.一种 Dijkstra 算法的优化实现算法-学术研究，2020.