离散数学 最短路径问题PPT课件

1、2021/3/91 例例: :如下图所示的单行线交通网，每个弧旁边的如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从数字表示这条单行线的长度。现在有一个人要从v1出出发，经过这个交发，经过这个交 通网到达通网到达v6 6， 要寻求总路要寻求总路 程最短的线程最短的线 路。路。 v6v5v3v1v4v23651124362021/3/92 从从v v1 1到到v v6 6的路线是很多的。比如从的路线是很多的。比如从v v1 1出发，出发，经过经过v v2 2 ,v,v4 4到达到达v v6 6或者从或者从v v1 1出发，经过出发，经过v v2 2，v v3 3，

2、v v5 5到达到达v v6 6等等。但不同的路线，经过的总长等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是不同的。例如，按照第一个线路，总长度是度是3+6+3=123+6+3=12单位，按照第二个路线，总长单位，按照第二个路线，总长度是度是3+1+1+6=113+1+1+6=11单位。单位。2021/3/93 寻求网络中两点间的最寻求网络中两点间的最短路就是寻求连接这两个点的边的短路就是寻求连接这两个点的边的总权数为总权数为最小的通路最小的通路。 管道铺设、交通网络、线管道铺设、交通网络、线路安排、厂区布局、设备更新等。路安排、厂区布局、设备更新等。2021/3/9

3、4在图的点或边上表明某种信息的数称为权。在图的点或边上表明某种信息的数称为权。含有权的图称为赋权图。含有权的图称为赋权图。二、赋权图的定义二、赋权图的定义如图如图2021/3/95 如果图中各点表示各个城市，边表示城市间的公如果图中各点表示各个城市，边表示城市间的公路，这就是一个公路交通网络图，路，这就是一个公路交通网络图，如果从如果从a点出发，目的地是点出发，目的地是z，那么如何寻求一条自点，那么如何寻求一条自点a到到z的通路，使通路上各边的权之和最小，的通路，使通路上各边的权之和最小，这就是赋权图的最短通路问题。这就是赋权图的最短通路问题。2021/3/96三、赋权图的最短通路三、赋权图的

4、最短通路l基本思想：先求出基本思想：先求出a到某一点的最短通路，到某一点的最短通路，然后利用这个结果再去确定然后利用这个结果再去确定a到另一点的最短通路，到另一点的最短通路，如此下去，直到找到如此下去，直到找到a到到z的最短通路为止。的最短通路为止。2021/3/97l若取若取T=e,f,g,z，点，点e关于关于T的指标的指标DT(e)就是由就是由a到到e 但不通过但不通过T中其中其 他点（即他点（即f,g,z）的所有通路中权和最小者。）的所有通路中权和最小者。目标集目标集设设V是图的点集，是图的点集，T是是V的子集，且的子集，且T 含有目标含有目标 z 但不含有但不含有a， 则称则称T为目标

5、集。为目标集。指标指标在目标集在目标集T中任取一点中任取一点 t ，由，由 a 到到 t 但不通过目标集但不通过目标集T中中 其他点的所有通路中各边权之和（简称为通路权和）的其他点的所有通路中各边权之和（简称为通路权和）的 最小者称为点最小者称为点 t 关于关于T 的指标，记为的指标，记为 DT(t)。2021/3/98用穷举法可得：用穷举法可得：a到到e 但不通过但不通过T中其他点（即中其他点（即f,g,z）的通路有：的通路有：a b e 权和为权和为10a b c e 权和为权和为9a c e 权和为权和为10a c b e 权和为权和为15a d c b e 权和为权和为18a d c

6、e 权和为权和为13由此可见：由此可见：e关于关于T的指标的指标DT(e) = 9 如图如图2021/3/99对于目标集对于目标集T=e,f,g,z，已用穷举法得到，已用穷举法得到e关于关于T的指标的指标DT(e) = 9 ，同样用穷举法可得，同样用穷举法可得f 关于关于T的指标的指标DT(f) = 6, g关于关于T的指标的指标DT(g) = 8，对于点，对于点z ，由于不存在，由于不存在a到到z但不通过但不通过T中其它点的通路，约定中其它点的通路，约定 。)(zDT比较比较T中四个点的指标可知：点中四个点的指标可知：点f 的指标最小，因此可得：的指标最小，因此可得：a 到到f 的最短通路权

7、和为的最短通路权和为DT(f) = 6。2021/3/910一般地，设一般地，设T=t1, t2, , tn，其中，其中t1为为T中指标最小的点，中指标最小的点，即即 DT(t1) =min(DT(t1) , DT(t2),DT(tn)则则a到到t1的最短通路的权和就是的最短通路的权和就是DT(t1) 。当得到目标集当得到目标集T中最小指标点中最小指标点t1后，如果后，如果 t1是目的地是目的地z，则问题得解。，则问题得解。如果如果t1不是目的地不是目的地z，则把，则把t1从从T中挖去，得到新的目标集中挖去，得到新的目标集T1，即即 T1=T-t1对于对于T1，又求出其各点的指标，并确定最小指

8、标点，如果这个最小，又求出其各点的指标，并确定最小指标点，如果这个最小指标点就是目的地指标点就是目的地z，则问题得解。如果不是目的地，则问题得解。如果不是目的地z，则把在，则把在T1中中又挖去这个最小指标点，得到新的目标集又挖去这个最小指标点，得到新的目标集T2，不断重复上述过程，不断重复上述过程，直到目的地直到目的地z为某个目标集的最小指标点为止。为某个目标集的最小指标点为止。由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。2021/3/911 以上用穷举法求目标集中各点的指标，思路简单，以上用穷举法求目标集中各点的指标

9、，思路简单，但方法不可取但方法不可取,特别是图中的点较多时。特别是图中的点较多时。下面介绍用递推的方法来求目标集中各点的指标。下面介绍用递推的方法来求目标集中各点的指标。2021/3/912如果已经求得目标集如果已经求得目标集T=t1, t2, , tn中各点的指标中各点的指标,设设t1为为T中指标最中指标最小的点，那么能推出小的点，那么能推出T1=T-t1中各点的指标中各点的指标.只须注意到只须注意到 t1已不属于目标集已不属于目标集T1,对于对于T1中与中与t1邻接的点邻接的点 t ,当寻求这点当寻求这点 t 的指标时的指标时, 将将a到到t1的最短通路再加上边的最短通路再加上边t1t所组

10、成的通路所组成的通路,也是一条由也是一条由a到到t但不通过但不通过T1中其他点的所有通路中其他点的所有通路.所以所以t关于关于T1的指标的指标 DT1(t) =min(DT(t), DT(t1)+W(t1,t)其中其中W(t1,t)是边是边t1,t上的权上的权. 对于对于T1中与中与t1不邻接的点不邻接的点 t2 , 那么它的指标没有发生变化那么它的指标没有发生变化,即即 DT1(t2) = DT (t2) 当当t1 和和t2不邻接时不邻接时,令令W(t1,t2)=,则则t2关于关于T1的指标也写作的指标也写作 DT1(t2) =min(DT(t2), DT(t1)+W(t1,t2)2021/

11、3/913设设T=e,f,g,z，已用穷举法求得，已用穷举法求得DT(e) = 9 ，DT(f) = 6, DT(g) = 8，DT(g) = , 其中其中f 是最小指标点是最小指标点,于是可得到于是可得到T1=T-f=e,g,z 的各点指标的各点指标:例如例如:如图如图DT1(e) =min(DT(e), DT(f)+W(f,e) =min(9, 6+2)=8DT1(g) =min(DT(g), DT(f)+W(f,g) =min(8, 6+6)=8DT1(z) =min(DT(z), DT(f)+W(f,z) =min(, 6+4)=10由以上分析可知由以上分析可知:当具有当具有n个点的目

12、标集个点的目标集Tn的各点指标求得时的各点指标求得时,就能推出就能推出n-1个点的目标集个点的目标集Tn-1=Tn-t1(t1是是T的最小指标的最小指标)的各点的指标的各点的指标.而初始情而初始情况的目标集况的目标集T1=V-a的各点指标容易求得的各点指标容易求得,因此求点的指标问题解决因此求点的指标问题解决.2021/3/914例例1 用狄克斯特洛算法求下列图中用狄克斯特洛算法求下列图中a 到到z的最短通路。的最短通路。比较以上各点的指标可知，比较以上各点的指标可知，b是最小指标点。但是最小指标点。但b不是目标不是目标点，所以挖去点，所以挖去b,于是可得：于是可得：解解 （1）首先取目标集）

13、首先取目标集T1=b,c,d,e,f,g,z， T1中各点的指标为：中各点的指标为： DT1(b) =2, (a b) DT1(c) =4, (a c) DT1(d) =3, (a d) DT1(e) = DT1(f) = DT1(g) = DT1(z)= 2021/3/915（2）令）令T2=T1-b=c,d,e,f,g,z，T2中各点的指标为：中各点的指标为：DT2(f)= min(DT1(f), DT1(b)+W(b,f)=min(, )= DT2(g)= min(DT1(g), DT1(b)+W(b,g)=min(, )= DT2(z)= min(DT1(z), DT1(b)+W(b,

14、z)=min(, )=比较以上各点的指标可知，比较以上各点的指标可知，d 是最小指标点。但是最小指标点。但 d 不是目标点，不是目标点，所以挖去所以挖去d ,于是可得：于是可得：DT2(c)=min(DT1(c), DT1(b)+W(b,c)=min(4,2+3)=4 (a c)DT2(d)= min(DT1(d), DT1(b)+W(b,d)=min(3,)=3 (a d)DT2(e)= min(DT1(e), DT1(b)+W(b,e)=min(,2+6)=8(a b e)2021/3/916（3）令）令T3=T2-d=c,e,f,g,z，T3中各点的指标为：中各点的指标为：DT3（z）=

15、min(DT2(z), DT2(d)+W(d,z)=min(,)=比较以上各点的指标可知，比较以上各点的指标可知，c是最小指标点。但是最小指标点。但c 不是目标点，不是目标点，所以挖去所以挖去c ,于是可得：于是可得：DT3（c）=min(DT2(c), DT2(d)+W(c,d)=min(4,3+2)=4 (a c)DT3（e）=min(DT2(e), DT2(d)+W(d,e)=min(8,)=8 (a b e)DT3（f）=min(DT2(f), DT2(d)+W(d,f)=min(,3+2)=5 (a d f )DT3（g）=min(DT2(g), DT2(d)+W(d,g)=min(

16、,3+7)=10(a d g )2021/3/917（4）令）令T4=T3-c=e,f,g,z，T4中各点的指标为：中各点的指标为：DT4（z）=min(DT3(z), DT3(c)+W(c,z)=min(,)= 比较以上各点的指标可知，比较以上各点的指标可知，f是最小指标点。但是最小指标点。但f不是目标点，不是目标点，所以挖去所以挖去f,于是可得：于是可得：DT4（e）=min(DT3(e), DT3(c)+W(c,e)=min(8,4+2)=6 (a c e)DT4（f）=min(DT3(f), DT3(c)+W(c,f)=min(5,4+6)=5 (a d f)DT4（g）=min(DT

17、3(g), DT3(c)+W(c,g)=min(10,4+7)=10(a d g)2021/3/918（5）令）令T5=T4-f=e,g,z，T5中各点的指标为：中各点的指标为：比较以上各点的指标可知，比较以上各点的指标可知，e是最小指标点。但不是目标点，是最小指标点。但不是目标点，所以挖去所以挖去e,于是可得：于是可得：DT5（e）=min(DT4(e), DT4(f)+W(f,e)=min(6,5+1)=6 (a c e或或a d f e) DT5（g）=min(DT4(g), DT4(f)+W(f,g)=min(10,5+6)=10 (a d g)DT5（z）=min(DT4(z), DT4(f)+W(f,z)=min(,5+5)=10 (a d f z)2021/3/919（6）令）令T6=T5-e=g,z，T6中各点的指标为：中各点的指标为：DT6（g）=min(DT5(g), DT5(e)+W(e,g)=min(10,)=10 (a d g)DT6（z）=min(DT5(z), DT5(e)+W(e,z)=min(10,6+3)=9 (a c e z 或或a d f e z)由于由于z是最小指标点是最小指标点,因此因此 a 到到 z 的最短通路为的最短通路为 ： (a c e z 或或a d f e z)如果在每求一次目标集