权和为10 权和为 权和为9 权和为 权和为10 权和为 权和为15 权和为 e 权和为 权和为18 权和为13 权和为
8
由此可见： 关于 的指标D 关于T的指标 由此可见：e关于 的指标 T(e) = 9
对于目标集T={e,f,g,z}，已用穷举法得到e关于 的指标 对于目标集 ，已用穷举法得到 关于T的指标 关于 DT(e) = 9 ，同样用穷举法可得 关于 的指标 T(f) = 6, 同样用穷举法可得f 关于T的指标 的指标D g关于 的指标 T(g) = 8，对于点 ，由于不存在 关于T的指标 关于 的指标D ，对于点z a到z但不通过 中其它点的通路，约定DT (z ) = ∞ 。 到 但不通过 中其它点的通路， 但不通过T中其它点的通路 比较T中四个点的指标可知： 的指标最小，因此可得： 比较 中四个点的指标可知：点f 的指标最小，因此可得： 中四个点的指标可知 a 到f 的最短通路权和为 T(f) = 6。 的最短通路权和为D 。
5
三、赋权图的最短通路
基本思想：先求出 到某一点的最短通路 到某一点的最短通路， 基本思想：先求出a到某一点的最短通路， 然后利用这个结果再去确定a到另一点的最短通路， 然后利用这个结果再去确定 到另一点的最短通路， 到另一点的最短通路 如此下去，直到找到 到 的最短通路为止 的最短通路为止。 如此下去，直到找到a到z的最短通路为止。
9
一般地， 中指标最小的点， 一般地，设T={t1, t2, …, tn}，其中 1为T中指标最小的点， ，其中t 中指标最小的点 即 DT(t1) =min(DT(t1) , DT(t2),…DT(tn))
则a到t1的最短通路的权和就是 T(t1) 。 到 的最短通路的权和就是D 当得到目标集T中最小指标点 是目的地z，则问题得解。 当得到目标集 中最小指标点t1后，如果 t1是目的地 ，则问题得解。 中最小指标点 如果t 不是目的地z，则把t 中挖去， 如果 1不是目的地 ，则把 1从T中挖去，得到新的目标集 1， 中挖去 得到新的目标集T 即 T1=T-{t1}
DT1(e) = DT1(f) = DT1(g) = DT1(z)=∞ 比较以上各点的指标可知， 是最小指标点 是最小指标点。 比较以上各点的指标可知，b是最小指标点。但b不是目标 不是目标 于是可得： 点，所以挖去b,于是可得： 所以挖去 于是可得
14
（2）令T2=T1-{b}={c,d,e,f,g,z}，T2中各点的指标为： ） ， 中各点的指标为： DT2(c)=min(DT1(c), DT1(b)+W(b,c))=min(4,2+3)=4 (a DT2(d)= min(DT1(d), DT1(b)+W(b,d))=min(3,∞)=3 (a DT2(e)= min(DT1(e), DT1(b)+W(b,e))=min(∞,2+6)=8(a 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 不是目标点，
2
一、问题的提法及应用背景
（1）问题的提法 问题的提法——寻求网络中两点间的最 寻求网络中两点间的最 短路就是寻求连接这两个点的边的总权数为 短路就是寻求连接这两个点的边的总权数为 最小的通路。 最小的通路。 （2）应用背景 应用背景——管道铺设、交通网络、线 管道铺设、 管道铺设 交通网络、 路安排、厂区布局、设备更新等。 路安排、厂区布局、设备更新等。
若取T={e,f,g,z}，点e关于 的指标 T(e)就是由 到e 但不通过 中其 ， 关于T的指标 就是由a到 但不通过T中其 若取 关于 的指标D 就是由 他点（ 他点（即f,g,z）的所有通路中权和最小者。 ）的所有通路中权和最小者。
7
如图
用穷举法可得： 到 但不通过T中其他点 中其他点（ 用穷举法可得：a到e 但不通过 中其他点（即f,g,z） ） 的通路有： 的通路有： a b a a a a a b c c d d e c e b c c e b e e
10
以上用穷举法求目标集中各点的指标，思路简单， 以上用穷举法求目标集中各点的指标，思路简单， 但方法不可取,特别是图中的点较多时。 但方法不可取 特别是图中的点较多时。 特别是图中的点较多时
下面介绍用递推的方法来求目标集中各点的指标。 下面介绍用递推的方法来求目标集中各点的指标。
11
如果已经求得目标集T={t1, t2, …, tn}中各点的指标 设t1为T中指标最 中各点的指标,设 如果已经求得目标集 中各点的指标 中指标最 小的点，那么能推出 中各点的指标. 中各点的指标 小的点，那么能推出T1=T-{t1}中各点的指标 已不属于目标集T 对于 中与t 对于T 只须注意到 t1已不属于目标集 1,对于 1中与 1邻接的点 t ,当寻求这点 t 当寻求这点 的指标时, 所组成的通路,也是一条由 的指标时 将a到t1的最短通路再加上边 1t所组成的通路 也是一条由 到t 到 的最短通路再加上边t 所组成的通路 也是一条由a到 但不通过T 中其他点的所有通路.所以 关于T 所以t关于 但不通过 1中其他点的所有通路 所以 关于 1的指标 DT1(t) =min(DT(t), DT(t1)+W(t1,t)) 其中W(t1,t)是边 1,t上的权 是边t 上的权. 其中 是边 上的权 对于T 中与t 那么它的指标没有发生变化, 对于 1中与 1不邻接的点 t2 , 那么它的指标没有发生变化 即 DT1(t2) = DT (t2)
6
目标集——设V是图的点集，T是V的子集，且T 含有目标 z 但不含有 ， 设 是图的点集 是图的点集， 是 的子集 的子集， 但不含有a， 目标集 则称T为目标集。 则称 为目标集。 为目标集 指标——在目标集 中任取一点 t ，由 a 到 t 但不通过目标集 中 在目标集T中任取一点 但不通过目标集T中 指标 在目标集 其他点的所有通路中各边权之和（简称为通路权和） 其他点的所有通路中各边权之和（简称为通路权和）的 关于T 的指标， 最小者称为点 t 关于 的指标，记为 DT(t)。 。
比较以上各点的指标可知， 是最小指标点 是最小指标点。 不是目标点， 比较以上各点的指标可知，c是最小指标点。但c 不是目标点，
16
所以挖去c 于是可得 于是可得： 所以挖去 ,于是可得：
（4）令T4=T3-{c}={e,f,g,z}，T4中各点的指标为： ） ， 中各点的指标为： DT4（e）=min(DT3(e), DT3(c)+W(c,e))=min(8,4+2)=6 (a ） DT4（f）=min(DT3(f), DT3(c)+W(c,f))=min(5,4+6)=5 (a ） DT4（g）=min(DT3(g), DT3(c)+W(c,g))=min(10,4+7)=10(a ） g) DT4（z）=min(DT3(z), DT3(c)+W(c,z))=min(∞,∞)=∞ ） 比较以上各点的指标可知， 是最小指标点 是最小指标点。 不是目标点 不是目标点， 比较以上各点的指标可知，f是最小指标点。但f不是目标点，
最短路径问题
如下图所示的单行线交通网， 例:如下图所示的单行线交通网，每个弧旁边的 数字表示这条单行线的长度。现在有一个人要从v 数字表示这条单行线的长度。现在有一个人要从 1出 发，经过这个交
v2
通网到达v 通网到达 6，
3
6 4 1
v4 3
要寻求总路 程最短的线 路。
v3 v1 5 v5 1 2
对于T 又求出其各点的指标，并确定最小指标点， 对于 1，又求出其各点的指标，并确定最小指标点，如果这个最小 指标点就是目的地z，则问题得解。如果不是目的地 ，则把在T 指标点就是目的地 ，则问题得解。如果不是目的地z，则把在 1中 又挖去这个最小指标点，得到新的目标集 不断重复上述过程， 又挖去这个最小指标点，得到新的目标集T2，不断重复上述过程， 直到目的地z为某个目标集的最小指标点为止。 直到目的地 为某个目标集的最小指标点为止。 为某个目标集的最小指标点为止 由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。 由此可见，求最短通路问题的关键是：如何求目标集中各点的指标。
v6 6
1
的路线是很多的。比如从v 出发， 从v1到v6的路线是很多的。比如从v1出发， 经过v 到达v 或者从v 出发，经过v 经过v2 ,v4到达v6或者从v1出发，经过v2，v3， 到达v 等等。但不同的路线， v5到达v6等等。但不同的路线， 经过的总长 度是不同的。例如，按照第一个线路， 度是不同的。例如，按照第一个线路，总长 度是3 单位， 度是3+6+3=12单位，按照第二个路线，总长 12单位 按照第二个路线， 度是3 度是3+1+1+6=11单位。 11单位。 单位
DT3（f）=min(DT2(f), DT2(d)+W(d,f))=min(∞,3+2)=5 (a ） DT3（g）=min(DT2(g), DT2(d)+W(d,g))=min(∞,3+7)=10(a ） g) DT3（z）=min(DT2(z), DT2(d)+W(d,z))=min(∞,∞)=∞ ）
13
用狄克斯特洛算法求下列图中a 的最短通路。 例1 用狄克斯特洛算法求下列图中 到z的最短通路。 的最短通路
解 （1）首先取目标集 1={b,c,d,e,f,g,z}， T1中各点的指标为： ）首先取目标集T ， 中各点的指标为： DT1(b) =2, DT1(c) =4, DT1(d) =3, (a (a (a b) c) d)ຫໍສະໝຸດ 3二、赋权图的定义