第八章-图与网络优化.pptVIP

V1 V2 V3 V4 6 2 1 4 8 V1 V2 V3 V4 6 2 1 4 8 4 无向图的处理：将原图中的每条边视为由方向相反的两条 PDF 文件使用 pdfFactory Pro 试用版本创建 ?w昀 弧组成，其权相等 最短路径算法 * 交通网络示意图 用Dijkstra法计算图示路网从节点1到节点9的最短路径。 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 * 步骤1 给定起点1的标号P[1]=0，其他节点标上了标号：T1(2)=…=T1(9)=∞ 步骤2 修改2、4点的T标号 T2(2)=min{T1(2)，P(1)+d12} =min{∞,0+2}=2 T2(4)=min{T1(4)，P(1)+d14} =min{∞,0+2}=2 在所有的T标号中，找出最小标号。2、4均为最小，任选其一，如节点2，即P[2]=2 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 P[1]=0 P[2]=2 T1(3)=∞ T1(6)=∞ T1(7)=∞ T1(8)=∞ T1(9)=∞ T2(4)=2 T1(5)=∞ * 步骤3 修改3、5点的T标号 T3(3)=min{T(3)，P(2)+d23} =min{∞,2+2}=4 T3(5)=min{T(5)，P(2)+d25} =min[∞,2+2]=4 在所有的T标号中，找出最小标号,节点4为最小，即P[4]=2 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 P[1]=0 P[2]=2 P[4]=2 T1(6)=∞ T1(7)=∞ T1(8)=∞ T1(9)=∞ T3(5)=4 T3(3)=4 * 步骤4 修改5、7点的T标号 T4(5)=min{T (5)，P(4)+d45} =min{∞,2+1}=3 T4(7)=min{T(7)，P(4)+d47} =min{∞,2+2}=4 在所有的T标号中，节点5为最小，即P[5]=3 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 P[1]=0 P[2]=2 P[4]=2 P[5]=3 T1(6)=∞ T4(7)=4 T1(8)=∞ T1(9)=∞ T3(3)=4 * 步骤5 修改6、8点的T标号 T5(6)=min{T (6)，P(5)+d56} =min{∞,3+1}=4 T5(8)=min{T(8)，P(5)+d58} =min{∞,3+2}=5 在所有的T标号中，节点3为最小，即P[3]=4 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 T4(7)=4 T5(8)=5 T1(9)=∞ P[4]=2 P[5]=3 T1(6)=4 P[1]=0 P[2]=2 P[3]=4 * 步骤6 修改6的T标号 T6(6)=min{T (6)，P(3)+d36} =min{4,4+2}=4 在所有的T标号中，节点6为最小，即P[6]=4 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 T4(7)=4 T5(8)=5 T1(9)=∞ P[4]=2 P[5]=3 P[6]=4 P[1]=0 P[2]=2 P[3]=4 * 步骤7 修改9的T标号 T7(9)=min{T (9)，P(6)+d69} =min{∞,4+2}=6 在所有的T标号中，节点7为最小，即P[7]=4 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 P[7]=4 T5(8)=5 T7(9)=6 P[4]=2 P[5]=3 P[6]=4 P[1]=0 P[2]=2 P[3]=4 ∞ * 步骤8 修改8的T标号 T8(8)=min{T (8)，P(7)+d78} =min{5,4+2}=5 在所有的T标号中，节点8为最小，即P[8]=5 7 6 9 8 5 3 2 4 1 1 2 2 2 2 2 1 2 2 2 2 2 P[7]=4 P[8]=5 T7(9)=6 P[4]=2 P[5]=3 P[6]=4 P[1]=0 P[2]=2 P[3]=4 * 步骤9 修改9的T标号 T9(