1 10 6
10 6 10 5 10 9
3 ∞ ∞ ∞ ∞ ∞
3 11 11 11 11 11
∞ ∞ ∞ ∞
∞ ∞ 14 13 13 13 9 8 11 11 ∞ ∞
11 16 11 11 16 16 16 15
所以最短路为 a e d h c g z
23
v1 … v2 t1 t2 DT(t1) T DT(t2)
与DT(t1)的最短性相矛盾！ 学会多画图,多从图形直观上来看.
d=W(av1…v2t2…t1)
定理 在有限赋权图G=(V,E)中,顶点a为起点,|V|=n+1, 递归地定义目标集 T1=V-{a},Ti+1=Ti-{ti} 即 Ti={ti,ti+1,…,tn}(i=1,2,…,n) 其中ti为Ti中指标最小者, 即 DTi(ti)= min{DTi(ti),DTi(ti+1),…,DTi(tn)}. 则 DTi+1(t) DTi(t),当t与ti不邻接 = min{DTi(t),DTi(ti)+W(ti,t)},当t与ti邻接
21
(4)由表可得最短路的长度为15.要得到最短路，
可以用逆向检查法：从Z开始，往上检查，直止 z的值发生变化为止，在此行中找到最小者，然 后由此最小者开始往上检查，直止发生变化， 在此行中找最小者，重复这一过程直止到a为止. 最后倒着把最小者所对应的点写成序列,此序列 即为最短路.
22
a
b c d e f g h i z
16
17
18
19
当我们比较熟练地掌握了狄克斯特洛算法后, 可用列表法来求最短路,它使求解过程显得十分 简洁.下面以一例来介绍此法. 例 求右图中a到z的最短路及其长度
20
方法： (1)先把T1=V-{a}中的点写在第一行上，把这些点 关于a的权相应地写在第二行上,并圈出其中最小 者b,相应值为1. (2)令T2=T1-{b},在第三行上先标出T1中与b不邻接 的点d,e,g,h, i, z，对于S1中与b 邻接的点c,f, 则用1+W(b,c),1+ W(b,f)与第二行c,f的值10与∞ 比较,然后取最小者写在第三行的相应位置,并圈出 最小点e及相应值3. (3)令T3=T2-{e},并其上的点写在第4行上,重复(2). 如此继续下去,直至z成为某个目标集的最小值为止.
由各Ti的构造过程知,则存在 DTi(t) 一条从a发的粉色的最短路径. 最终, 从a出发的到t的粉色路径的权和 ≤ 从a出发的到t的黄色路径的权和
由上面的分析可知, 当t与ti邻接时,
DTi+1(t)
DTi(ti)+W(ti,t) ti Ti a Ti+1 … t
DTi(t)
=min{DTi(t),DTi(ti)+W(ti,t)},
设赋权图 G=(V,E),u,v∈V,从u到v所带权 的总和最小的通路,称为u到v的最短通路.
例
2
2、问题与求法 如何求一权图中任意两点间的最短路？这 里介绍狄克斯特洛算法(Dijkstra's algorthm.)
4
3、迪克斯特洛算法
5
T
a … t z
权和最小记为DT(t)
6
例
T
a→c→e权和为10
7
8
9
10
定理 在赋权图G=(V,E)中,起点a∈V-T,设目标集 T={t1,t2,…,tn},且t1为T中指标最小者, 即DT(t1)= min{DT(t1),DT(t2),…,DT(tn)}, 则a到t1的最短通路的权和为DT(t1). 证明 采用反证法.证明思路如右图所示. 若d<DT(t1),即黄色线比紫色线短, a 则从图形直观上则有 DT(t2)≤W(av1…v2t2)<d<DT(t1)
{
(i=1,2,…,n-1)
ห้องสมุดไป่ตู้
证明
当t与ti不邻接
a
Ti ti Ti+1
如右图所示可知 DTi+1(t)=DTi(t)
t DTi+1(t)=DTi(t)
当t与t1邻接时
DTi(ti) 如由图所示， 设黄线为a到ti的最短路径 a 若存在绿色边 … 则黄线与绿线也构成从 a到t的一条路径.
ti Ti W(tT i,t) i+1 t
赋权图的最短通路
1、赋权图 设G=(V,E)是有限图,如果对E中的每一条边e, 都有一个实数W(e)附着其上,则称G为赋权图,则称 W(e)为边e的权.
a
例 右图就是一个赋权图.
a
14
a
12
a
b 13 c
d a
a
9
d a
a
d a
e
a
7
d
a
10
d
a
5
d
a
a
6a
d a
8
d a
a
11
d a
d
a
1
对于赋权图 G=(V,E),规定: