第8章图第8讲-最短路径和Dijkstra算法.ppt

第8章图第8讲-最短路径和Dijkstra算法.ppt考虑带权有向图,把一条路径(仅仅考虑简单路径)上所经边的权值之和定义为该路径的路径长度或称带权路径长度。
路径的概念
从源点到终点可能不止一条路径,把路径长度最短的那条路径称为最短路径。
最短路径
v
v1
v2
u
c1
c2
c3

cm
路径长度=c1 + c2 + …+ cm
路径:(v,v1,v2,…,u)
1/21
问题描述:给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。
从一个顶点到其余各顶点的最短路径
单源最短路径问题: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
每一步求出v到U中一个顶点u的最短路径,并将u移动到S中。直到U为空。
(1)初始化:,S只包含源点即S={v},v的最短路径为0。U包含除v外的其他顶点,U中顶点i距离为边上的权值(若v与i有边<v,i>)或∞(若i不是v的出边邻接点)。
狄克斯特拉算法的过程
S
v
U=V-S
i
v与U中顶点i的边
4/21
(2)从U中选取一个距离v最小的顶点u,把u加入S中(该选定的距离就是v  u的最短路径长度)。
S
v
U=V-S
u
v与U中顶点u的边最小
5/21
(3)以u为新考虑的中间点,修改U中各顶点j的最短路径长度:若从源点v到顶点j(j∈U)的最短路径长度(经过顶点u)比原来最短路径长度(不经过顶点u)短,则修改顶点j的最短路径长度。
S
v
U=V-S
u
j
两条路径进行比较:
若经过u的最短路径长度更短,则修正
6/21
顶点v  j的最短路径长度=MIN(cvk+wkj,cvj)
S
v
U=V-S
u
j
u
v
j
...
cvu
……
cvj
边wuj
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的最短路径
?
v
u
j
…
a
…
a
v
u
…
…
v
u
j
…
a
…
b
反证法证明:
而通过b的路径更短,则v →… a →… u → j不是最短路径
是v  u的最短路径
与假设矛盾,问题得到证明。
v  j最短路径中j的前一个顶点
10