-
Dijkstra
算法描述
目录
一、算法概述
.
................................................ .................................................. ................................
2
二、算法原理及计算
.
.............................................
..................................................
.......................
2
2.1
算法原理
............
..................................................
..................................................
.............
2
2
.2
计算过程
......................
..................................................
..................................................
...
2
2.3
< br>改进的算法（
Dijkstra-
like
）分析
.
< br>............................................... ......................................
5
三、源码分析
.
................................................ .................................................. ................................
5
四、接口调用
.
................................................ .................................................. ................................
6
一、算法概述
Dijkstra
（迪杰斯特拉）算法是典型的单源最短路径计算算法，用于解决源
点
到所有结点最短路径计算的问题，它采用了分治和贪心（动态规划的特殊形式）
的思想搜索全局最优解。
本系统采用了主流
、
开源的
JA
V
A
图论库
——
Jgrapht
来解决源点到终点间所
有可能路径输出的问题，它的核心计算引擎采用
了一种
Dijkstra-like
算法，由经
典的
Dijkstra
（迪杰斯特拉）算法演化和改进
而来。
二、算法原理及计算
2.1
算法原理
Dijkstra
算法思想为：设
G
?
(
V
,
?
E
)
是带权有向图，
< br>V
代表图中顶点集合，
E
代表图
中含权重的边集合。
将全部顶点集合
V
分成两组，
第一组为已求出最短路
径的顶点集合，
用
S
表示
（初始时
S
中只有一个源点，
以后每求得一条最短路径，
就将该路径的终点加入到集合
S
中）<
/p>
；
第二组为其余待确定最短路径的顶点集合，
用
U
表示。
按最短路径长度的递增
次序依次把
U
集合的顶点逐个加入到
S
集合中，
约束条件是保持从源点
v
到
S
中各顶点的最短路径长度不大于从源点
v
到
U
中任<
/p>
何顶点的最短路径长度。算法的终止条件是集合
U
为空集，即集合
U
的顶点全
部
加入到集合
S
中。
2.2
计算过程
以图
1
为例讨论
Dijkstra
算法的计算过程，即计算某源点到网络上其余各结
点的最短路径
，
设源点为①，
逐步搜索，
每次找出一
个结点到源点①的最短路径，
直至完成所有结点的计算。
4
2
2
3
3
3
1
1
2
2
1
6
< br>2
4
1
5
3
图
1
带权有向图
记
D
(
v
)
为源点①到某终点
v
的距离，是源点①
到终点
v
某条路径的所有链路
长度之和
。记
l
(
w
,
?
v
)
是源点
w
到终点
v
的
距离。
Dijkstra
算法归纳如下：
（
1
）初始化，令
S
是已求出最短路径的顶点集合，
S
< br>?
?
?
?
，
U
是其余未确
定最短路径的顶点集
合，
U
?
?
?
????
?
，可写出：
?
l
(1,
v
)
(1-1)
D
(
v
)
?
?
?
?
公式
1-1
中，
l
(1,
v
)
是源点①与终点
v
的直连路径长度，而
?
代表源点①与终
点
v
不相连
,
初始化结果如表
1
所示；
（
2
）遍历集合
U
中的所有结点
v
并计算
min
?
D
(
v
),
D
(
w
)
?
l
(<
/p>
w
,
v
)
?
。所有结点
中寻找一个结点
w
，用最小值
min
?
D
(
v
),
D
(
w
)
?
l
(
w
< br>,
v
)
?
去更新
D
(
v
)
值，并将其从
集合
U
中剔除并加入到集合
S
中。
（
3
）重复步骤（
2
）
，直至集合
U
为空集。
表
1
针对图
1
的最短路径计算过程
步骤
初始化
1
2
3
4
5
S
①
①④
①④⑤
①④⑤②
①④⑤②③
①④⑤②③⑥
U
②③④⑤⑥
②③⑤⑥
②③⑥
③⑥
⑥
D(2)
2
2
2
Add
2
2
D(3)
4
4
3
3
Add
3
D(4)
1
Add
1
1
1
1
D(5)
∞
2
Add
2
2
2
D(6)
∞
4
4
4
4
Add
表
1
是针对
图
1
的详细计算步骤的中间结果。具体计算描述如下：
初始化步骤：由于初始选择了源点①，因此集合
S
只是结点①。观察图
1
，
源点①到结点②、③、④的直连路径长度分别为
2
，
4
和
1
，
到结点⑤、⑥不存
在直连边因而为
?
。
根据计算结果，集合
U
所有结点
D
(
w
)
的最小值为
D
(4)
，因
而将结点④从集合
U
中剔除并将其加入到集合
< br>S
中
步骤
1
：
<
/p>
针对结点②，
v
?
2,
w
?
4
（
v
是遍历集合
U
的某结点，
w
是集合
S
新加入结
点）
，
D
(
v
)
?
D
(2)
?
2
，而
D
(
w
)
?
l
(
< br>w
,
v
)
?
D
(4)
?
l
(4,2)
?
1
< br>?
2
?
3
?
D
(2)
，因而源
-
-
-
-
-
-
-
-
-
上一篇：常用数学术语
下一篇：体心立方晶格紧束缚近似能带结构的计算机模拟