D ijkstra 算法的优化

遇 娜,简广宁

(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]=∞。引进一个辅助向量D ist并设VS为起始点,每个分量D ist[i]表示已找到的从起始点VS到每个终点Vi的最小权值。则该向量的初始值为:D ist[i]=Cost[S,i]V i∈V。其中,V是结点的集合。令S为已经找到的从起点出发的最短路径的终点集合,初始值为S={VS},则从VS出发到图G上其它所有结点Vi可能达到的最短路径长度为D ist[i]=Cost[S,i]V i∈V。

(1)选择V j,使得D[j]=m in{D[i]|V i∈V-S}。V j就是当前求得的一条从VS出发的最短路径的终点,令S=S∪{V j}。

(2)修改从VS到集合V-S中任意一顶点V K的最短路径长度。如果D[j]+Cost[j,k]

(3)修改D ist[k]为D isk[k]=D ist[j]+Cost[j,k];重复第2、3步操作共 N-1次,由此求得从VS到其他顶点的最优路径,该路径是各权值递增的序列。

2.算法分析

通过对该算法的仔细分析与研究可以得出,上述算法中有几点不足之处:

(1)用邻接矩阵Cost来存储网络图,其存储量为N×N。对于大型稀疏矩阵,这将耗费大量资源存储那些无意义的矩阵元素。

(2)当从未标记节点集合(V-S)选定下一个节点V j作中间节点后,在更新操作过程中,需要扫描所有的未标记节点并进行比较更新。而未标记节点集合(V-S)中往往包含大量与中间节点V j不直接相连的节点。

(3)在选择下一个最短路径节点作为中间节点时,需要比较所有的未标记节点,而这个中间节点往往包含在与已标记节点S集合的所有节点邻接的节点中。

(4)在算法的每次迭代中,由于未标记节点以无序的形式存放在一个链表中或一个数组中,每次选择最短路径节点都必须将所有未标记节点扫描一遍,当节点数目很大时,这无疑将成为制约计算速度的关键因素。

二、Dijkstra算法的优化

针对Dijkstra算法存在的问题,我们在数据的组织和存储以及最短路径节点的选取上,进行了改进。

1.优化思路分析

(1)数据组织和数据存储

用邻接矩阵存储图需要开辟N×N(N为节点数目)的存储空间,对于一个大型稀疏图来说,计算效率和存储效率都很低。所以可以采用邻接表来存储网络拓扑结构以节省存储空间。

(2)节点排序和最短路径节点的选取

在改进算法中,初始时,待排序的节点以无序形式连续序存放在一个一维数组中,对其进行堆排序,调整成小顶堆后,各节点即是以完全二叉树的顺序存储结构形式存储,0号单元存放的即是调整后的堆顶元素,后面依次以左子树、右子树。在调整堆的过程中时间复杂度为O(logN),(N为待排序节点个数)。与从无序结构下的数组或链表中选择下一个最短路径节点相比较,明显地节约了时间,提高算法执行效率。

2.改进的Dijkstra算法基本思想

设置两个集合S和adj及一个数组T[],S是已标记集合,adj是邻接点集,T[]存储待排序节点。初始状态时,S={V 0},T[]=adj[V 0],首先,将数组 T[]通过堆排序调整为小顶堆,取数组首元即堆顶节点current为中间节点,并将current加入到已标记集合S中;再次,比较更新current的邻接点集合与已标记集合的差集(A dj[current]-S)中任一节点V i的当前最短路径值;然后查找S集合所有节点的邻接点的并集与S集合的差集(∪adj[S])-S),同时将这些节点顺次存入数组T中,覆盖原数组中的节点,并设置一个计数器i记录节点个数;最后将数组中的前i个元素按它们当前的最短路径值调整成小顶堆,取堆顶节点为下一个最短路径节点将其归并到集合S中。如此反复迭代循环,直到所有的节点都加入到集合S中。下面用Dijkstra算法求图G中节点V 0到其它各节点的最短路径D[V],图G以邻接表为存储结构。

三、复杂性分析与比较

1.空间复杂度分析

对于数据的存储传统的Dijkstra算法采用图论中的邻接矩阵方法,其存储量为N×N(N为网络图中的节点数),通常的网络图尽管节点很多,但与节点相关联的节点数目并不多,一般都为稀疏图,这样该存储方法将浪费大量的空间,而且在计算时亦要花费大量的时间遍历无意义的数据。而本文的改进算法采用了邻接表的链式存储结构,对于一个无向图来说,其存储量为O(E+2N)(E为节点列表中同节点关联的所有弧段数目)。另外还使用了两个数组,其中一个数组D[V]用来存储所求得源点到其它所有节点的最短路径值,另外一个数组 T[V]用来暂存待排序节点。所以总的空间复杂度为O(E+4N)。与传统Dijkstra算法相比较,节省了空间,提高了存储效率。

2.时间复杂度分析

传统D ijkstra算法采用广度优先的搜索策略,在访问了网络中所有的节点后,最终生成从源点到其余各点的最短路径树。该算法在选择最短路径节点时需要访问所有的未标记节点,效率低下,整个算法的运行时间为O(N×N)。而改进的Dijkstra算法而改进算法的主要步骤查找待排序节点和堆排序上,因待排序节点为所有已标记节点的邻居节点的并集与标记集合的差集(∪adj[S])-S),所以这个步骤的运行时间主要取决于已标记节点的邻节点集合元素数量的多少(而该数量值往往小于未标记集合中的元素个数),查找次数最多为E次。在排序过程中,每次调整的时间复杂度不会超过满二叉树的高度logN。这两个过程共需迭代执行N次,因此整个算法理论上最长运行时间仅为O(N(logN+E))。当网络拓扑结构图具有的节点数N较大且其关联矩阵为一个稀疏矩阵时,相对传Di2 jkstra算法,优化算法大大减少了计算次数与比较次数,在一定程度上提高了运算速度。

四、结论

传统D ijkstra算法使用的是邻接矩阵来存储网络图,存储量为N×N,而使用邻接表来存储网络数据信息,可使存储空间减少至N量级。另外,利用堆排序来选择最短路径节点,只处理标记节点的相邻节点,从而大量减少了要计算的节点数,最终使得算法的时间复杂度由原来的O(N 2)降至O(N(logN+E))。随着网络中节点数目和边数的增多,这种改进的Dijkstra算法越来越显示出其优势,可使算法所需的时间明显减少,并获得精度较高的结果。

[1]王战红,孙明明,姚瑶.Dijkstra算法程序的优化与实现[J].湖北第二师范学院学报2008,(08).

[2]李臣波.一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报2008,(13).

[3]杜兴勇,刘延平,王忠文.Dijkstra算法程序的优化与实现[J].通化师范学院学报,2008,(12).

A bs tra c t:Dijkstra algorithm is used to find the shortest path between various nodes at the right value in a given graph.In many p rojects it serves as the rationale for solving the shortest path p roblem.On the basis of an analysis of traditional Dijkstra algorithm’s design philosophy,the paper p resents some of its defects in imp lementation and puts forw ard some suggestions for imp rovement for the purpose of saving memory space and increasing efficiency.Furthermore,by comparison of their comp lexity analy2 sis,it p roves that the imp roved algorithm is superior to the traditional one in efficiency.

Key word s:shortest path;Dijkstra algorithm;adjacency list;heap sort

The Op tim ization of Dijkstra Algo rithm

YU Na1,JIAN Guang -ning2
(1.Tianjin Hongqiao District Staff and Workers University,Tianjin 300131 China;2.Tianjin U rban Construction Institute,Tianjin 300384 China)

TP312

A

1673-582X(2011)02-0089-03

2010-11-10

遇娜(1977-),女,天津市人,天津市红桥区职工大学讲师,从事计算机方面的教学与研究。