基于数据结构的最短路径算法的研究

2022-09-12

最短路径就是通过计算在众多的路线中找到一条最短的路径。但是数据结构中的最短路径与我们平时意义上的地理位置上的最短路径不同, 数据结构上的最短路径还要根据实际需要, 考虑到交通路线的选择、管道的铺设等问题。所以, 在城市的规划和交通物流领域都要重要意义[1]。因此, 数据结构的最短路径算法的研究成为现今较热的话题, 如何对其进行应用, 成为了相关工作人员需要深思的问题。

一、图论的基本概念

就图的定义而言, 图, 英文为graph, 是一种数据结构, 它较线性表和树更为复杂。图与线性表和树的结构的区别表现在结点的关系上, 在线性表中, 每一个结点都有一个前驱结点和后继节点 (首位结点出外) , 并且结点与结点之间属于一对一的对应关系。树上的结点都有与它对应的父结点和一个甚至多个孩子结点, (叶子结点出外) , 结点与结点之间的属于一对多的关系。与上述两种结点方式不同, 图中的结点关系是多对多, 结点与结点之间能够互相连接, 每个结点可以选择进行连接, 或者不进行连接。

图的存储结构有很多种, 邻接矩阵、邻接表、邻接多重表、十字邻接表。除了存储图中各个顶点的信息之外, 还要存储顶点与顶点之间的关系。

二、数据结构的最短路径算法的思路分析

首先, 定义简单的加权图G=, 假设V0, ..., Vm-1, Vm属于V, 其中Vi-1, V1为边 (弧) 上得结点;序列V0, ...V1, ...Vm, 表示结点V0到结点Vm之间的路径。路径长度用W01+W12+....+W (n-1) n来表示。所以, 结点V0到结点Vm之间的最短路径长度就是结点V0到结点Vm之间的最短路径。

其次, G=, 假设V0, ..., Vm-1, Vm属于V, 图G的邻接矩阵为A= (aij) 。

式中wij表示Vi与Vj之间的边权值。

最后, 通过上述的分析能够看出Dijkstra的算法就是对路径进行更替, 并根据递增的路径长度与次序, 得到最短路径, 即[2]:

三、Dijkstra的算法

(一) 传统Dijkstra的算法

传统的Dijkstra的算法就是利用路径的长度增递次序进行最短路径的计算, 主要的方式就是通过一个源结点的不断增长, 以此来寻找最短路径。上文分析的最短路径的寻找方式就是根据传统Dijkstra的算法。但是传统的Dijkstra的算法也表现出了严重的不足之处。在Dijkstra的算法中主要是依据标记法来寻找最短的路径, 就是指在未标记点中寻找权值最小的结点。但是这样的方式会导致一种现象就是, 当未标记结点以一种没有规律可循的方式进行排列, 如果面对图集的较大数据的计算时, 就会为最短路径的计算速度造成限制。严重时会发生系统瘫痪的情况。因此, 优化Dijkstra的算法是解决这样问题的当务之急。

(二) 优化后的Dijkstra的算法

优化Dijkstra的算法主要从以下几个方面入手:

1. 优化思路分析

在Dijkstra的算法中要实现网络图中未标记各个结点到最短距离结点的转变。通过转变大量存储无序为标记结点的扫描, 并在结点中找到最短路径。但是这样大数据的计算就必然会影响数据运算的速度。因此, 优化的想法就是通过扫描结点, 根据结点的标号数值进行排序, 这样符合要求的阶段通过一次整合排序就能够得到, 并且进行有效的计算, 大大提升了计算的速率。

2. 优化方法

优化方法主要从两个方面进行:一是, 根据GIS图形成网络拓扑图, 并对图中的重要数据、参数进行设置与计算。算法存储的方式主要是面对对象进行设置。如表1所示。二是, 利用JAVA平台计算最短路径, 图中信息每一个对象元素都要与之对应一个关键字, 利用crit Hash的对象类特征, 通过将每一个结点到其他结点的最短路径进行封装, 并进行关键字的命名, 能够缩短搜索范围。

(三) Dijkstra算法的应用

Dijkstra的算法能够应用在城市的交通网络中, 要想寻找一个地点到另一个地点的最短路径, 就利用这样的算法进行实现。电子地图就是利用的这样原理。首先要思考, 在地图上从某地到某地绝对不止一条路径, 但是在多条路径中, 要区分什么路径是可行路径, 什么路径最短路径, 还要根据距离的远近进行交通工具的计算与选择。通过数学建模, 将起始地点与终点进行定位采用抽象的计算算法, 构建数据模型:

定义简单的加权图G=, V表示所有站点的集合, 假设有M个站点;E表示直接路径的结合, 假设有N条路径。但是还要注意的一点就是每条路径的方向性和可通行。最后通过排除对保留路径进行距离值和时间的计算。

除此之外, Dijkstra算法还能够运用在城市管道铺设、物流等领域上, 并通过自身的优化使工作变得更加的简单、便捷。

四、结论

数据结构的最短路径算法的研究在增强数据结构的分析能力、提高寻找最短路径的方法上有着积极的作用。在此过程中, 通过对传统Dijkstra算法的分析, 结合实际操作中的问题, 对其进行优化。能够提升寻找并计算最短路径的计算是效率与计算时间, 不断的促进数据结构的最短路径算法能力的提升。

摘要：数据结构的最短路径的研究是图论中最重要的一部分知识, Dijkstra算法作为最短路径计算的基础理论, 被广泛的应用到各个方面。鉴于此, 本文以图论的基本概念作为出发点, 分析数据结构的最短路径算法的思路, 重点探讨了Dijkstra算法的不足, 并进行优化。旨在不断提升基于数据结构的最短路径算法的研究质量献力。

关键词：数据结构,最短路径,研究,算法