最新-第四章图论-2-课件.ppt

1、第三节 最短路问题一、标号法一、标号法 两个固定点之间的最短路两个固定点之间的最短路 二、距离矩阵法二、距离矩阵法 任意点之间的最短路任意点之间的最短路 标号法标号法计算步骤 （1）.初始化 （永久标号P，临时标号T）设：起点设：起点V Vs s，终点，终点V Vt t，其他点，其他点V Vi i起点起点V Vs s：P(VP(VS S)=0)=0其他点其他点V Vi i：T(VT(Vi i)=)=计算停止判别标准：终点计算停止判别标准：终点V Vt t获得了获得了P P标号（永久标号）标号（永久标号）例例V1V2V3V462148初始化初始化V1标上标上P标号，标号，P(V1)=0其他节点标

2、上其他节点标上T标号：标号：T(V2)=,T(V3)=T(V4)=P(V1)=0T(V2)=T(V3)=T(V4)=（2 2）.计算、修改计算、修改T T标号标号 设刚得到设刚得到P P标号的节点为标号的节点为V Vi i，考虑所有与，考虑所有与V Vi i相联的相联的T T标号点标号点V Vj j，修改，修改V Vj j的的T T标号标号 ijdiPjTjT)(),(min)(P(Vi)V1V2V3V462148修改修改T T标号：标号：V V1 1节点为刚得到节点为刚得到P P标号的节点标号的节点与之相连的节点是与之相连的节点是V V2 2、V V3 3T(V2)=min(,P(V1)+d

3、12)=min(,0+6)=6P(V1)=0T(V3)=min(,P(V1)+d13)=min(,0+2)=2P(V1)=0T(V2)=6T(V3)=2T(V4)=ijidVPjTjT)(),(min)(（3 3）.确定确定P P标号标号在所有在所有T T标号节点中，选择标号最小的节点，标号节点中，选择标号最小的节点，将其将其T T标号改为标号改为P P标号。标号。V1V2V3V462148T(V4)=T(V2)=6T(V3)=2V V3 3节点节点T T标号值最小，标号值最小，将其修改成将其修改成P P标号标号P(V3)=2P(V1)=0T(V2)=6T(V3)=2T(V4)=P(V3)=2

4、（4 4）.重复重复2 23 3步骤，直到终点得到步骤，直到终点得到永久永久P P标号。标号。V1V2V3V462148修改修改T T标号：标号：V V3 3节点为刚得到节点为刚得到P P标号的节点标号的节点与之相连的节点是与之相连的节点是V V2 2、V V4 4T(V2)=min(6,P(V3)+d32)=min(6,2+1)=3P(V3)=2T(V4)=min(,P(V3)+d34)=min(,2+8)=10P(V1)=0T(V2)=3P(V3)=2T(V4)=10V1V2V3V462188T(V2)=3T(V4)=10V V2 2节点节点T T标号值最小，标号值最小，将其修改成将其修改

5、成P P标号标号P(V2)=3P(V1)=0T(V2)=3T(V4)=10P(V3)=2P(V2)=3V1V2V3V462188修改修改T T标号：标号：V V2 2节点为刚得到节点为刚得到P P标号的节点标号的节点与之相连的节点是与之相连的节点是V V4 4T(V4)=min(10,P(V2)+d24)=min(10,3+8)=10P(V2)=3P(V1)=0P(V2)=3P(V3)=2T(V4)=10这时只有一个这时只有一个T T标号节点：标号节点：V V4 4将将V V4 4的的T T标号改成标号改成P P标号标号V1V2V3V462148P(V4)=7计算停止，从计算停止，从V V1

6、1到到V V4 4的的最短路为最短路为7 7个单位。个单位。P(V1)=0P(V2)=3P(V3)=2T(V4)=7P(V4)=7 最短路径追踪：最短路径追踪：P(VP(V4 4)=P(V)=P(V2 2)+d)+d2424，记录记录V V2 2VV4 4 P(VP(V2 2)=P(V)=P(V3 3)+d)+d3232，记录记录V V3 3VV2 2 P(VP(V3 3)=P(V)=P(V1 1)+d)+d1313，记录记录V V1 1VV3 3 所以，从所以，从V V1 1VV4 4的最短路径为的最短路径为 V V1 1VV3 3VV2 2VV4 4最短路问题的两个结果：最短路权 最短路径

7、V1V2V3V462148 最短路径追踪：最短路径追踪：P(V4)=P(V2)+d24，记录，记录V2V4 P(V2)=P(V3)+d32，记录，记录V3V2 P(V3)=P(V1)+d13，记录，记录V1V3 所以，从所以，从V1V4的最短路径为的最短路径为 V1V3V2V4计算停止判别标准：计算停止判别标准：对于求对于求V VS SVVt t的最短路，的最短路，V Vt t标上标上P P标号时标号时计算停止；计算停止；对于求对于求V VS S所有点的最短路，所有点标所有点的最短路，所有点标上上P P标号时计算停止。标号时计算停止。对于标号法的说明对于标号法的说明（1 1）.路权为负值时失效

8、（交通网络中一般路权为负值时失效（交通网络中一般不存在）不存在）（2 2）.对于无向图对于无向图（将原图中的每条边视（将原图中的每条边视为由方向相反的两条弧组成，其权相等。为由方向相反的两条弧组成，其权相等。V1V2V3V462148V1V2V3V4621484无向图的处理：将原图中的每条边视为由方向相反的两条无向图的处理：将原图中的每条边视为由方向相反的两条 弧组成，其权相等弧组成，其权相等距离矩阵法距离矩阵法 适用条件：任意点之间的最短路任意点之间的最短路 1、构造距离矩阵、构造距离矩阵D=dD=dijij 之间直接连接权值之间不直接连接ji,ji,ji 0ijdV1V2V3V462148

9、0 8 0 1 4 0 2 6 00DD Dijij的含义：当前从的含义：当前从i i节点节点直接直接到到j j节点的距离节点的距离 2、矩阵迭代计算、矩阵迭代计算11iijidDnkdddikjiikiij,2,1,min1 3、终止判别条件、终止判别条件（n为节点数量）为节点数量）1mmDDV1V2V3V4621480 8 0 1 4 0 2 6 00Dnkdddikjiikiij,2,1,min10 8 0 1 4 0 10 2 3 01D3 ,12,06,60min ,min042014032013022012012011112dddddddddK=1K=2K=3K=4V1V2V3V4621480 8 0 1 4 0 2 6 00D0 8 0 1 4 0 10 2 3 01D0 5 0 1 4 0 7 2 3 02D0 5 0 1 4 0 7 2 3 03DD D3 3=D=D2 2，计算停止，计算停止教材83页，例5.5表5-1VtVsV3V1V4V2314237316请分别采用标号法和请分别采用标号法和距离矩阵法求解距离矩阵法求解V Vs sVVt t的最短路的最短路作业作业