第四章 图论-2.pptVIP

例 （2）. 计算、修改T标号 设刚得到P标号的节点为Vi，考虑所有与Vi相联的T标号点Vj，修改Vj的T标号 （3）.确定P标号 （4）.重复2~3步骤，直到终点得到永久P标号。 最短路径追踪： P(V4)=P(V2)+d24，记录V2→V4 P(V2)= P(V3)+d32，记录V3→V2 P(V3)= P(V1)+d13，记录V1→V3 所以，从V1→V4的最短路径为 V1→V3→V2→V4 最短路径追踪： P(V4)=P(V2)+d24，记录V2→V4 P(V2)= P(V3)+d32，记录V3→V2 P(V3)= P(V1)+d13，记录V1→V3 所以，从V1→V4的最短路径为 V1→V3→V2→V4 计算停止判别标准： 对于求VS→Vt的最短路，Vt标上P标号时计算停止； 对于求VS→所有点的最短路，所有点标上P标号时计算停止。 对于标号法的说明 （1）. 路权为负值时失效（交通网络中一般不存在） （2）. 对于无向图—（将原图中的每条边视为由方向相反的两条弧组成，其权相等。 距离矩阵法 适用条件：任意点之间的最短路 1、构造距离矩阵 2、矩阵迭代计算 * * 第三节 最短路问题 一、标号法 两个固定点之间的最短路 二、距离矩阵法 任意点之间的最短路 标号法 标号法计算步骤 （1）. 初始化 （永久标号P，临时标号T） 设：起点Vs，终点Vt，其他点Vi 起点Vs： P(VS)=0 其他点Vi：T(Vi)=∞ 计算停止判别标准：终点Vt获得了P标号（永久标号） V1 V2 V3 V4 6 2 1 4 8 初始化 V1标上P标号，P(V1)=0 其他节点标上T标号： T(V2)=∞, T(V3)=∞ T(V4)=∞ P(V1)=0 T(V2)=∞ T(V3)=∞ T(V4)=∞ P(Vi) V1 V2 V3 V4 6 2 1 4 8 修改T标号： V1节点为刚得到P标号的节点 与之相连的节点是V2、V3 T(V2)=min(∞,P(V1)+d12) =min(∞,0+6)=6 P(V1)=0 T(V3)=min(∞,P(V1)+d13) =min(∞,0+2)=2 P(V1)=0 T(V2)=6 T(V3)=2 T(V4)=∞ 在所有T标号节点中，选择标号最小的节点， 将其T标号改为P标号。 V1 V2 V3 V4 6 2 1 4 8 T(V4)=∞ T(V2)=6 T(V3)=2 V3节点T标号值最小， 将其修改成P标号 P(V3)=2 P(V1)=0 T(V2)=6 T(V3)=2 T(V4)=∞ P(V3)=2 V1 V2 V3 V4 6 2 1 4 8 修改T标号： V3节点为刚得到P标号的节点 与之相连的节点是V2、V4 T(V2)=min(6,P(V3)+d32) =min(6,2+1)=3 P(V3)=2 T(V4)=min(∞,P(V3)+d34) =min(∞,2+8)=10 P(V1)=0 T(V2)=3 P(V3)=2 T(V4)=10 V1 V2 V3 V4 6 2 1 8 8 T(V2)=3 T(V4)=10 V2节点T标号值最小， 将其修改成P标号 P(V2)=3 P(V1)=0 T(V2)=3 T(V4)=10 P(V3)=2 P(V2)=3 V1 V2 V3 V4 6 2 1 8 8 修改T标号： V2节点为刚得到P标号的节点 与之相连的节点是V4 T(V4)=min(10,P(V2)+d24) =min(10,3+8)=10 P(V2)=3 P(V1)=0 P(V2)=3 P(V3)=2 T(V4)=10 这时只有一个T标号节点：V4 将V4的T标号改成P标号 V1 V2 V3 V4 6 2 1 4 8 P(V4)=7 计算停止，从V1到V4的 最短路为7个单位。 P(V1)=0 P(V2)=3 P(V3)=2 T(V4)=7 P(V4)=7 最短路问题的两个结果：最短路权 最短路径 V1 V2 V3 V4 6 2 1 4 8 V1 V2 V3 V4 6 2 1 4 8 V1 V2 V3 V4 6 2 1 4 8 4 无向图的处理：将原图中的每条边视为由方向相反的两条 弧组成，其权相等 D=[dij] V1 V2 V3 V4 6 2 1 4 8 Dij的含义：当前从i节点直接到j节点的距离 3、终止判别条件 （n为节点数量）