- 1 -
中国科技论文在线
基于 Dijkstra 的一种优化算法
张凯，白雪**
作者简介：张凯，（1990-），男，大学生，主要研究方向：软件工程。
通信联系人：白雪，（1983-），女，助教，主要研究方向：软件工程
（辽宁工程技术大学软件学院，辽宁 葫芦岛 125105）
摘要：现如今最短路径问题在运输等其他路径选择中有着广泛的应用，而传统的 Dijkstra5
算法在求解节点间最短路径时，对已标识节点外的节点进行了大量额外的运算，从而影响了
算法速度。针对这一问题，本文基于传统的 Dijkstra 算法提出了一种优化方案。该优化算
法在更新扩展顶点到剩余节点的最短路径值时，通过图的邻接表仅对当前扩展顶点的相邻节
点操作，而不涉及到其他节点。而且，将此传统问题分解成从首尾分别求解的两个子问题。
因此优化算法减少了计算的次数，在复杂的网路图中，能够有效地提高了算法的速度。 10
关键词：Dijkstra 算法；最短路径；改进算法
中图分类号：
An optimized algorithm based on Dijkstra algorithm
Zhang Kai, Bai Xue 15
(Software Engineering,Liaoning Technical University, LiaoNing HuLuDao 125105)
Abstract: Now the shortest path problem in the transport and other path selection has a wide range
of applications, and when it comes to nodes that have been identified outside of the nodes,
Traditional Dijkstra's algorithm for solving the shortest path has a large number of additional
operations, thus affecting the speed of the algorithm. To solve this problem, this paper based on 20
the traditional Dijkstra's algorithm proposed an optimization program. The optimization algorithm
to update the remaining nodes expanded vertex value of the shortest path through the graph
adjacency list of vertices adjacent only to the current expansion node operation, without involving
other nodes. Moreover, This traditional problem split into two sub-problems which start from the
beginning and end. Therefore, the optimization algorithm in a complex network diagrams, can 25
reduce the number of calculations and effectively improve the speed of the algorithm.
Keywords: Dijkstra's algorithm; Shortest path; Optimized algorithm
0 引言
在计算机科学领域，最短路径问题一直是研究的焦点问题之一，也是图论研究中的一30
个经典算法问题。随着社会的不断进步，最短路径算法在人们的日常生活中也显得越来越
重要，诸如物资运输、交通咨询、公路收费系统[1]等问题在人们的日常生活中非常常见，由
此可见对最短路径问题的研究是非常有意义的。
最短路径问题是旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
经典最短路径算法层出不穷，著名的算法有 Dijkstra 算法[2]、A*算法[3]、SPFA 算法[4]、35
Bellman-Ford 算法[5]、Floyd-Warshall 算法[6]和 Johnson 算法等。其中最为常用的是 Dijkstra
算法，本文在对传统 Dijkstra 算法分析的基础上，对其进行了优化。优化算法只对当前扩
展顶点的相邻顶点做处理，而不涉及到其他顶点，并运用分治思想将传统问题分解，最终达
到提高算法速度的目的。本文安排如下：第一部分介绍经典 Dijkstra 算法基本原理。第二部
分介绍本文所提及的算法思想并予以实例分析。第四部分得出本文的结论。 40
1 经典 Dijkstra 算法基本原理
通常采用 Dijkstra(迪杰斯特拉)算法来求解最短路径的问题，其主要特点是以起始点为
- 2 -
中国科技论文在线
中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法的思想是：设有两个顶点集合 S 和
T，集合 S 中存放图中已经找到最短路径的顶点，集合 T 中存放图中剩余顶点。初始状态时，
集合 S 中只包含原点 Vo，然后不断从集合 T 中选取到顶点 Vo路径长度最短的顶点 Vu并入45
到集合 S 中。集合 S 每并入一个新的顶点 Vu，都要修改顶点 Vo到集合 T 中顶点的最短路径
长度值。不断重复此过程，直到集合 T 中顶点全部并入到 S 中为止。
算法步骤描述如下[1]：
1) 假设用带权的邻接矩阵 arcs 来表示一个带权图，arcs[i][j]表示弧<Vi ,Vj>上的权值。
若<Vi ,Vj>不存在，则置 arcs[i][j]为∞。S 为已找到从 V 出发的最短路径的终点的50
集合，它的初态为空集。那么，从 V 出发到图上其余顶点 Vi可能达到的最短路径
长度的初值为：D[i] = arc[Locate Vex(G,v)[i]，Vi∈V
2) 选择 Vj，使得 D[j] = Min{ D[i] | vi∈V-S }，Vj就是当前求得的一条从 v 出发的最
短路径的终点。令 S = S ∪ { j }
3) 修改从 V 出发到集合 V-S 上任一顶点 Vk 可达的最短路径长度。如果 D[j] + 55
arcs[j][k]<D[k]，则修改 D[k]为 D[k] = D[j]+arcs[j][k]
4) 重复操作 2）、3）共 n -1 次。由此求得从 V 到图上其余各个顶点的最短路径是
依路径权值递增的序列。
从以上描述可知：实现 Dijkstra 算法主要是从未标记的节点中选择一个权值最小的链路
作为下一个转接点，并更新此顶点到剩余顶点的最短路径长度值。因此，在图中有大量顶点60
的情况下就需要反复扫描顶点，必将成为制约算法效率的关键因数。
2 基于 Dijkstra 算法的改进
算法改进的思路
传统的 Dijkstra 算法能得出最短路径的最优解，但是在大量节点的情况下它遍历
计算的节点很多，所以效率低，其主要表现在：更新新加入顶点 Vj到剩余顶点的最短65
路径长度值时，需要大量比较 D[j] + arcs[j][k]和 D[k]的大小，而此时很多顶点并不与 Vj
相邻（arcs[j][k]＝∞），增加了额外的运算量。在实际问题应用中，考虑到 Dijkstra 算法是
从起点到终点求最短路径,同样也可以表述为从终点到起点求最短路径。因此求短路径问题
是否可以分解为由起点到终点求解最短路径和由终点到起点求解最短路径两个子问题。这样
可以降低问题复杂度,符合并行处理的思想。 70
算法的步骤描述如下：
STEP1 :初始化。用 arcs[i][j]表示弧<Vi ,Vj>上的权值，若<Vi ,Vj>不存在，则置 arcs[i][j]
为∞；S =Φ，Q =Φ，S、Q 分别是由起点 V0和终点 Vn开始的扩展顶点的集
合，Vm、Vn 分别是集合 S、Q 的当前扩展顶点；用带权连通图的邻接表表示
此图，D[i]、E[i]分别表示起点到 Vm、终点到 Vn的最短路径 75
STEP2 :选择 Vm、Vn，使得 D[i] = Min{ D[i] | vm∈S }、D[j] = Min{ D[j] | vn∈Q }。通过
邻接表查找当前扩展顶点的相邻顶点的权值，修改当前扩展顶点到剩余顶点的
最短路径值。
STEP3 :重复 STEP2 步骤，当且仅当 Vm = Vn，此时就已寻找出最短路径。
STEP4 :计算最短路径。L = D[m] + D[n]。 80
- 3 -
中国科技论文在线
算法实例分析
如图所示：在物流配送过程中，需要将货物从 S 城市运送到 F 城市，途中需停靠多个
城市。图中的顶点表示城市，权值表示城市之间的路程。配送员需要选择最优的停靠城市，
使得运送的路程最短。
85
图 1 交通网路图
Fig. 1 Transportation network map
以下是图对应的邻接表，用于在比较 D[j] + arcs[j][k]和 D[k]的大小时，减少计算量。
90
图 2 网络图的邻接表
Fig. 2 Network adjacency table
传统的 Dijkstra 算法搜索过程，如下：
95
表 1 Dijkstra 搜索过程
Tab. 1 Dijkstra search process
Dist[] 步骤 已并入顶点 剩余顶点
S A B C D E F
1 S A B C D E F 0 4 6 6 ∞ ∞ ∞
2 S A B C D E F 0 4 5 6 11 ∞ ∞
3 S A B C D E F 0 4 5 6 11 9 ∞
4 S A B C D E F 0 4 5 6 11 9 ∞
5 S A B C E D F 0 4 5 6 10 9 17
6 S A B C E D F 0 4 5 6 10 9 16
7 S A B C E D F 无剩余顶点 0 4 5 6 10 9 16
- 4 -
中国科技论文在线
改进算法的搜索过程，如下：
100
表 2 改进算法搜索过程
Tab. 2 The search process of optimized algorithm
步骤 集合 S 集合 Q 当前扩展顶点 最短路径
1 S F S F 0
2 S A F D A D 4+6
3 S A B F D E B E 10+1+1
4 S A B E 12+4
由此可见 :通过改进后的算法和传统的 Dijkstra 算法所求的最短路径相同，都为 :
S->A->B->E->D->F，大小为 16。 105
传统 Dijkstra 算法从顶点出发，通过权值迭代遍历所有其他节点后，最后得到从顶点到
其他各顶点的最短路径树。它在提取最短路径节点时需要访问所有的未标记节点以及更新最
短路径值，所以算法的运行时间为 O（N2）。本文提出的改进算法在更新最短路径值时与
选择最短路径值最小的节点时，仅仅与到当前扩展顶点的邻居集合有关，其运行时间取决于
当前扩展顶点的邻居集合的元素数量多少。而且，改进的算法将此问题分解为两个子问题进110
行求解，符合分治思想。当网络拓扑结构图具有的节点数 N 较大且其关联矩阵为一个稀疏
矩阵时，相对传统的 Dijkstra 算法，优化算法大大减少了比较次数，在一定程度上提高了运
算速度。
3 结论
本文分析了经典 Dijkstra 算法的思想及其不足之处，针对传统 Dijkstra 算法的不足之处，115
对其进行了优化处理。本文提出的优化算法在更新当前扩展顶点到剩余顶点的最短路径时仅
对扩展顶点的相邻顶点做处理，同时运用分治思想将传统问题分解，当遇到网络图规模较大
及其关联矩阵为一个稀疏矩阵时，这种优化算法与传统 Dijkstra 算法相比，能大大减少了
计算次数及比较次数，提高了运算效率。当然这种优化算法还有很多不足之处，比如说：在
算法的实现方面存在困难，且这种优化的适用范围受到约束。在以后的研究中将对这些问题120
作更进一步的分析，找出更好的解决方案 。
[参考文献] (References)
[1] 黄贤英，李玉桃，张本强. 最短路径搜索算法在高速公路收费系统中的应用[N].重庆工学院学报, 2007, 3.
[2] 严蔚敏，吴伟明. 数据结构[M]. 北京：清华大学出版社，2009. 125
[3] 焦学军，秦奋，王海鹰. A 星算法在城镇地价评估中的应用[D]. 郑州：河南大学中澳地理信息分析与应
用中心，2008.
[4] 段凡丁. 关于最短路径的 SPFA 快速算法[D]. 成都：西南交通大学计算中心，1994.
[5] 陈华容，张崇富. Bellman-Ford 算法的改进研究[N]. 电子科技大学学报,2006, 2.
[6] Anany Levition. The design and Analysis of Algorithms[M]. 潘彦. 北京：清华大学出版社，2007. 130
