最短路径Dijkstra算法.ppt

a
1
1
最短路径
两点之间的最短路径问题：
求从某个源点到其余各点的最短路径
每一对顶点之间的最短路径
a
2
求
从源点到其余各点的最短路径
的算法的基本思想
:
依
最短路径的长度
递增的次序求得各
条路径
v
1
源点
v
2
…
其中，
从源点到
顶点
v
的最短路径
是所有最短路径
中长度最短者。
a
3
2 Dijkstra
算法
单源最短路径问题是：
给定带权的有向图
G=
（
V
，
E
），源点
v
∈
V
，求从
v
到
V
中其余各顶点的最短路径。
70
源点
终点
V1
V2
最短路径
（
V0
，
V2
，
V3
，
V1
）
（
V0
，
V2
）
（
V0
，
V2
，
V3
）
（
V0
，
V2
，
V3
，
V1
，
V4
）
—
路径长度
45
10
25
55
∞
0
20
10
50
1
10
35
4
V0
15
20
3
V3
30
V4
2
15
3
5
V5
如何求解上图中的最短路径问题，
Dijkstra
提出了一种解决方案。
a
4
即迪杰斯特拉算法，其基本思想如下：
设置辅助数组
Dist
，其中每个分量
Dist[k]
表示
当前所求得的从源点到其余各顶点
k
的最短路
径的长度。
1
）在所有从源点出发的弧中选取一条权值最小
的弧，即为第一条最短路径。
G
.
arcs
[
v
0
][
k
]
V0
和
k
之间存在弧
?
Dist
[
k
]
?
?
V0
和
k
之间不存在弧
?
INFINITY
a
5
2
）设置一个顶点集合
S
，存放最短路径的终点。
顶点
k
为当前最短路径的终点
,
将
V
k
加入集合
S
中，而
Dist[k]
为最短路径的长度。
3
）每次从集合
V-S
中取出具有最短特殊路径长
度的顶点
u
，将
u
加到
S
中，同时对数组
Dist
做必
要的修改。
若
Dist
[
u
]+

[
u
][
k
]<
Dist
[
k
]
则将
Dist
[
k
]
改为
Dist
[
u
]+

[
u
][
k
]
。
其中，
特殊路径
指从源点到
u
中间只经过
S
中顶
点的路径。
4)
重复操作
2
）、
3
）共
n-1
次。由此求得图上其
a
6
余各顶点的最短路径是依路径长度递增的序列。
若带权图
G
如下所示，根据上述算法来
求解源点
v0
到
v2
的最短路径。
3
1
25
2
8
0
5
30
20
10
12
4
3
4
1
25
3
3
0
30
8
8
∞
∞
4
4
12
2
3
a
7
根据以上分析和举例，不难得出狄杰斯