离散数学---最短路径问题

1例:如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v6，要寻求总路程最短的线路。v6v5v3v1v4v2365112436最短路径问题2从v1到v6的路线是很多的。比如从v1出发，经过v2,v4到达v6或者从v1出发，经过v2，v3，v5到达v6等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是3+6+3=12单位，按照第二个路线，总长度是3+1+1+6=11单位。3一、问题的提法及应用背景（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。（2）应用背景——管道铺设、交通网络、线路安排、厂区布局、设备更新等。4在图的点或边上表明某种信息的数称为权。含有权的图称为赋权图。二、赋权图的定义如图5如果图中各点表示各个城市，边表示城市间的公路，这就是一个公路交通网络图，如果从a点出发，目的地是z，那么如何寻求一条自点a到z的通路，使通路上各边的权之和最小，这就是赋权图的最短通路问题。6三、赋权图的最短通路基本思想：先求出a到某一点的最短通路，然后利用这个结果再去确定a到另一点的最短通路，如此下去，直到找到a到z的最短通路为止。7若取T={e,f,g,z}，点e关于T的指标DT(e)就是由a到e但不通过T中其他点（即f,g,z）的所有通路中权和最小者。目标集——设V是图的点集，T是V的子集，且T含有目标z但不含有a，则称T为目标集。指标——在目标集T中任取一点t，由a到t但不通过目标集T中其他点的所有通路中各边权之和（简称为通路权和）的最小者称为点t关于T的指标，记为DT(t)。8用穷举法可得：a到e但不通过T中其他点（即f,g,z）的通路有：abe权和为10abce权和为9ace权和为10acbe权和为15adcbe权和为18adce权和为13由此可见：e关于T的指标DT(e)=9如图9对于目标集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的最短通路权和为DT(f)=6。10一般地，设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，又求出其各点的指标，并确定最小指标点，如果这个最小指标点就是目的地z，则问题得解。如果不是目的地z，则把在T1中又挖去这个最小指标点，得到新的目标集T2，不断重复上述过程，直到目的地z为某个目标集的最小指标点为止。由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。11以上用穷举法求目标集中各点的指标，思路简单，但方法不可取,特别是图中的点较多时。下面介绍用递推的方法来求目标集中各点的指标。12如果已经求得目标集T={t1,t2,…,tn}中各点的指标,设t1为T中指标最小的点，那么能推出T1=T-{t1}中各点的指标.只须注意到t1已不属于目标集T1,对于T1中与t1邻接的点t,当寻求这点t的指标时,将a到t1的最短通路再加上边t1t所组成的通路,也是一条由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))13设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个点的目标集Tn的各点指标求得时,就能推出n-1个点的目标集Tn-1=Tn-{t1}(t1是T的最小指标)的各点的指标.而初始情况的目标集T1=V-{a}的各点指标容易求得,因此求点的指标问题解决.14例1用狄克斯特洛算法求下列图中a到z的最短通路。比较以上各点的指标可知，b是最小指标点。但b不是目标点，所以挖去b,于是可得：解（1）首先取目标集T1={b,c,d,e,f,g,z}，T1中各点的指标为：DT1(b)=2,(ab)DT1(c)=4,(ac)DT1(d)=3,(ad)DT1(e)=DT1(f)=DT1(g)=DT1(z)=∞15（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,z))=min(∞,∞)=∞比较以上各点的指标可知，d是最小指标点。但d不是目标点，所以挖去d,于是可得：DT2(c)=min(DT1(c),DT1(b)+W(b,c))=min(4,2+3)=4(ac)DT2(d)=min(DT1(d),DT1(b)+W(b,d))=min(3,∞)=3(ad)DT2(e)=min(DT1(e),DT1(b)+W(b,e))=min(∞,2+6)=8(abe)16（3）令T3=T2-{d}={c,e,f,g,z}，T3中各点的指标为：DT3（z）=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(ac)DT3（e）=min(DT2(e),DT2(d)+W(d,e))=min(8,∞)=8(abe)DT3（f）=min(DT2(f),DT2(d)+W(d,f))=min(∞,3+2)=5(adf)DT3（g）=min(DT2(g),DT2(d)+W(d,g))=min(∞,3+7)=10(adg)17（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(ace)DT4（f）=min(DT3(f),DT3(c)+W(c,f))=min(5,4+6)=5(adf)DT4（g）=min(DT3(g),DT3(c)+W(c,g))=min(10,4+7)=10(adg)18（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(ace或adfe)DT5（g）=min(DT4(g),DT4(f)+W(f,g))=min(10,5+6)=10(adg)DT5（z）=min(DT4(z),DT4(f)+W(f,z))=min(∞,5+5)=10(adfz)19（6）令T6=T5-{e}={g,z}，T6中各点的指标为：DT6（g）=min(DT5(g),DT5(e)+W(e,g))=min(10,∞)=10(adg)DT6（z）=min(DT5(z),DT5(e)+W(e,z))=min(10,6+3)=9(acez或adfez)由于z是最小指标点,因此a到z的最短通路为：(acez或adfez)如果在每求一次目标集各点的指标时把各点通过的路径记录下来就可得到a到z的最短通路.最短通路权和为9。20例2用列表法求出上例中a到z的最短通路。21解：bcdefgz243∞∞∞∞4883∞∞∞4510∞6510∞6101091022练习：用列表法求出a到z的最短通路。