第三步:若网络图中已无7标号点,停止 计算。否则,令T(vn)=min(v) v;∈s 然后将V的T标号改成P标号,转入第 二步。 此时,要注意将第二步中的v改为vb
第三步：若网络图中已无T标号点，停止 计算。否则,令 , 然后将 的T 标号改成P 标号 ，转入第 二步。 此时，要注意将第二步中的 v1 改为 。 0 j v ( ) min ( ) 0 j v s j T v T v j = 0 j v
例5-3用狄克斯拉算法 求解图5-1所示最短路问题。 4 5 3 图51例53网络图
例5-3 用狄克斯拉算法 求解图5-1所示最短路问题。 4 v1 v2 v3 v4 v6 v5 v7 2 2 5 6 1 4 1 3 4 1 2 图5-1 例5-3网络图
解:先将图5-1的网络用矩阵形式表示出来: V10 5 246 5 0 D 20246 10414 40 4120
解：先将图5-1的网络用矩阵形式表示出来: − − − − − − − − − − − − − − − − − − = 4 1 2 0 3 1 0 2 6 4 0 1 4 1 0 4 1 4 5 2 0 1 3 2 0 2 4 6 0 2 5 7 6 5 4 3 2 1 V V V V V V V D 1 v 2 v 3 v 4 v 5 v 6 v 7 v
步骤考察点T标号点集标号(表P标号) 6 2V. 2+ 2+ 3V2 M4……:x.…114+1 4+ 8 4 5+45÷5+ ≤ 8 5V 6≤1v5 6+ 8 6 5
步骤 考察点 T标号点集 标 号（ 表P标号） 1 v1 {v2，…，v7 } v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+2 0+5 2 5 - - - - 2 3 4 5 6 v2 v3 v4 v5 v6 {v3，…，v7 } {v4，…，v7 } {v5，v6，v7 } {v5，v7 } 2+2 2+4 2+6 4 6 8 - - 4+1 4+3 5 8 7 - 5+4 5+1 5+4 8 6 9 6+2 8 8 {v7 } 8+1 8
反向追踪,得到最优路线: 3→V4-V v5 讨论:若先把v的标号改为永久性标号, 该怎麽继续作下去?
反向追踪，得到最优路线： v1 v2 v3 v4 v6 v7 v5 讨论：若先把v7的标号改为永久性标号， 该怎麽继续作下去？