离散数学 最短路径问题.ppt

* 例:如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交 通网到达v6， 要寻求总路 程最短的线 路。 v6 v5 v3 v1 v4 v2 3 6 5 1 1 2 4 3 6 最短路径问题 * 从v1到v6的路线是很多的。比如从v1出发，经过v2 ,v4到达v6或者从v1出发，经过v2，v3，v5到达v6等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是3+6+3=12单位，按照第二个路线，总长度是3+1+1+6=11单位。 * 一、问题的提法及应用背景 （1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。 （2）应用背景——管道铺设、交通网络、线路安排、厂区布局、设备更新等。 * 在图的点或边上表明某种信息的数称为权。 含有权的图称为赋权图。 二、赋权图的定义 如图 * 如果图中各点表示各个城市，边表示城市间的公 路，这就是一个公路交通网络图， 如果从a点出发，目的地是z，那么如何寻求一条自点 a到z的通路，使通路上各边的权之和最小， 这就是赋权图的最短通路问题。 * 三、赋权图的最短通路 基本思想：先求出a到某一点的最短通路， 然后利用这个结果再去确定a到另一点的最短通路， 如此下去，直到找到a到z的最短通路为止。 * 若取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)。 * 用穷举法可得：a到e 但不通过T中其他点（即f,g,z） 的通路有： a b e 权和为10 a b c e 权和为9 a c e 权和为10 a c b e 权和为15 a d c b e 权和为18 a d c e 权和为13 由此可见：e关于T的指标DT(e) = 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中其它点的通路，约定 。 比较T中四个点的指标可知：点f 的指标最小，因此可得： a 到f 的最短通路权和为DT(f) = 6。 * 一般地，设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为某个目标集的最小指标点为止。 由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。 * 以上用穷举法求目标集中各点的指标，思路简单， 但方法不可取,特别是图中的点较多时。 下面介绍用递推的方法来求目标集中各点的指标。 * 如果已经求得目标集T={t1, t2, …, tn}中各点的指标,设t1为T中指标最 小的点，那么能推出T1=T-{t1}中