13-图及网络规划.ppt

第十章 图与网络优化 主要内容: 图论的基本概念 最小支撑树问题 最短路问题 最大流问题 最小费用最大流问题 1,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, ∞ 4,11 1,1 M, ∞ M, ∞ M, ∞ 1,3 1,6 1,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, ∞ 4,11 1,1 M, ∞ M, ∞ M, ∞ 1,3 3,5 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, ∞ 4,11 1,1 M, ∞ M, ∞ 1,3 M, ∞ 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 M, ∞ 2,6 M, ∞ 1,3 M,∞ 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 M, ∞ 2,6 M, ∞ 1,3 M,∞ 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 M, ∞ 2,6 5,12 1,3 5,9 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 M, ∞ 2,6 5,12 1,3 5,9 2,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1,1 M, ∞ 2,6 5,12 1,3 5,9 5,10 2,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1,1 M, ∞ 2,6 5,12 1,3 5,9 5,10 例 用Dijkstra算法求前面例子中从v1到v8的最短路。 i=0 给发点v1以P标号，令S0={v1}，P(v1)=0，λ(v1)=0， 其余各点均给T标号，T(vi)=+ ? ，λ(vi)=M，(i=2,3,…,9) 从v1出发,考察以v1为出发点且与其相邻的所有具有T标号 的点v2，v3，v4 v2 v5 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 对v2,有T(v2)=min{T(v2), P(v1)+w12}=min{+ ? ,0+6}=6 同时修改λ(v2)=1 同理有， T(v3)=3， λ(v3)=1 ； T(v4)=1， λ(v4)=1； 比较所有T标号， T(v4)=1最小， P(v4)=1，S1={v1，v4} v2 v5 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 v2 v5 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 i=1 从刚得到P标号的点v4出发,考察以v4为出发点且与 其相邻的所有具有T标号的点v6， T(v6)=min{T(v6), P(v4)+w46}=min{+ ? ,1+10}=11， 同时修改λ(v6)=4 比较所有T标号， T(v3)=3最小， P(v3)=3， S2={v1，v4，v3} v2 v5 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 i=2 从刚得到P标号的点v3出发,考察以v3为出发点且与 其相邻的所有具有T标号的点v2， T(v2)=min{T(