遇 娜,简广宁

(1.天津市红桥区职工大学,天津市 300131;2.天津城市建设学院,天津市 300384)

D ijkstra 算法的优化

遇 娜1,简广宁2

(1.天津市红桥区职工大学,天津市 300131;2.天津城市建设学院,天津市 300384)

Dijkstra算法是许多工程解决最短路径问题的理论基础,可用来找出图中指定节点到其他节点的最短距离,有着广泛的应用。文章通过分析传统Dijkstra算法的设计思想,提出该算法在实现方法上存在的一些不足之处,并从节约存储空间和提高运算效率方面对其进行了改进,并通过复杂性分析比较,得出这种改进算法的效率优于传统的Dijkstra算法。

最短路径 ;D ijkstra算法;邻接表;堆排序

最短路径问题是图论研究中一个重要课题。传统公认的求最短路径最好的算法是D ijkstra算法,它是由荷兰著名的计算机科学家艾兹格·迪科斯彻提出来的,可用来找出图中指定节点到其他节点的最短距离。其主要思想是从源点求出长度最短的一条路径,然后通过对路径长度迭代得到从源点到其他目标节点的最短路径。但随着所解决问题规模的增大,应用传统的D ijkstra算法会使时间和空间复杂度不断加大。因此,需对传统的Dijkstra算法进行了改进,提出采用邻接表和堆排序的一种新的优化方法。

一、传统的D ijkstra算法

1.算法的基本思想

D ijkstra算法用于计算一个源节点到所有其他节点的最短代价路径,它是按路径长度递增的次序来产生最短路径的算法。下面以邻接矩阵描述Dijkstra算法的实现过程。假设用带权的邻接矩阵Cost来表示具有N个结点的带权有向图G[3],Cost[i,j]表示弧的权值,如果从Vi到V j不通,则Cost[i,j]=∞。……