第8章图第8讲-最短路径和Dijkstra算法.ppt
文本预览下载声明
考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度。
8.5.1 路径的概念
从源点到终点可能不止一条路径，把路径长度最短的那条路径称为最短路径。
8.5 最短路径
路径长度=c1 + c2 + … + cm
路径：（v，v1，v2，… ，u）
1/21
问题描述：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。
8.5.2 从一个顶点到其余各顶点的最短路径
单源最短路径问题：Dijkstra算法
2/21
设G=(V，E)是一个带权有向图， 把图中顶点集合V分成两组：
狄克斯特拉（Dijkstra）求解思路
S
v
U=V-S
u
第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，… ，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。
第2组为其余未求出最短路径的顶点集合（用U表示）。
3/21
（1）初始化：，S只包含源点即S={v}，v的最短路径为0。U包含除v外的其他顶点，U中顶点i距离为边上的权值（若v与i有边v，i）或∞（若i不是v的出边邻接点）。
狄克斯特拉算法的过程
4/21
（2）从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是v u的最短路径长度）。
S
v
U=V-S
u
5/21
（3）以u为新考虑的中间点，修改U中各顶点j的最短路径长度：若从源点v到顶点j（j∈U）的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点j的最短路径长度。
S
v
U=V-S
u
j
6/21
顶点v j的最短路径长度＝MIN(cvk+wkj，cvj)
S
v
U=V-S
u
j
v j的路径：
不经过顶点u
经过顶点u
修改方式
7/21
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
v
j
考虑中间其他所有顶点k，通过比较得到v j的最短路径
k
8/21
如何存放最短路径长度：
用一维数组dist[j]存储！
源点v默认， dist[j]表示源点 顶点j的最短路径长度。如dist[2]=12表示源点 顶点2的最短路径长度为12。
如何存放最短路径：
从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0 5的最短路径为0、2、3、5，表示为
path[5]={0,2,3,5}。
所有n-1条最短路径可以用二维数组path[][]存储。
？
算法设计（解决2个问题）
9/21
改进的方法是采用一维数组path来保存：
若从源点v j的最短路径如下：
则
一定是从源点v u的最短路径
？
b
反证法证明：
而通过b的路径更短，则v → … a → … u → j不是最短路径
与假设矛盾，问题得到证明。
10
从path[j]推出的逆路径：j，w，u，v
对应的最短路径为：v → u → w → j
v
w
j
u
v j的最短路径:
11/21
0
1
3
2
4
5
6
4
7
6
1
6
8
5
6
6
2
4
1
S U dist[] path[]
0 1 2 3 4 5 6
0 1 2 3 4 5 6
{0}
{1,2,3,4,5,6}
{0, 4, 6, 6, ∞, ∞, ∞}
{0, 0, 0, 0, -1, -1, -1}
{0,1}
{2,3,4,5,6}
{0, 4, 5, 6, 11, ∞, ∞}
{0, 0, 1, 0, 1, -1, -1}
{0,1,2}
{3,4,5,6}
{0, 4, 5, 6, 11, 9, ∞}
{0, 0, 1, 0, 1, 2, -1}
Dijkstra算法示例演示
12/21
0
1
3
2
4
5
6
4
7
6
1
6
8
5
6
6
2
4
1
S U dist[] path[]
0 1 2 3 4 5 6
0 1 2 3 4 5 6
{0,1,2}
{3,4,5,6}
{0, 4, 5, 6, 11, 9, ∞}
{0, 0, 1, 0, 1, 2, -1}
Dijkstra算法示例演示
{0,1,2,
显示全部