运筹08（第六章图与网络分析）.pptVIP

运筹学OPERATIONS RESEARCH 对 v2 标号，将 L12 的值标注在 v2 旁的小方框内； 将( v1, v2) 加粗，并令 V∪v2 →V， L1p = min { L12+d25 , L12+d24, L13+d34 ,L13+d36 } =min{5+7,5+2,2+7,2+4} = 6 = L16 。 (4) 同 v1 , v2 ,v3 相邻的未标号点有v4 、 v5、 v6 ， 对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将( v3, v6) 加粗，并令 V∪v6 →V， L1p = min { L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 } =min{5+7, 5+2, 2+7, 6+2, 6+1, 6+6} = 7 = L14 = L15 (5) 同 v1 , v2 ,v3 , v6 相邻的未标号点有v4 、 v5、 v7 ， 对 v4 , v5 同时标号，将 L14 = L15 的值标注在 v4, v5 旁的小方框内；将( v2, v4), ( v6, v5) 加粗，并令V∪v4∪v5→V， L1p = min { L15+d57 , L16+d67 } =min{7+3,6+6}=10= L17 (6) 同 v1 , v2 ,v3 , v4, v5, v6 相邻的未标号点只有 v7 ， 对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将( v5, v7) 加粗。图中粗线表明从点 v1 到网络中其它各点的最短路，各点旁的数字就是点 v1 到各点的最短距离。 二. 求任意两点间最短距离的矩阵算法 用 Dijkstra 算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。 例. 利用矩阵算法求上述网络图中各点间的最短距离。 解. 设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =∞，显然 dii =0。建立距离矩阵： 从上述距离矩阵可以看出从 i 点到 j 点的直接距离，但从 i 到 j 的最段距离不一定就是从 i 点直接到 j 点。 如上述问题中，从 v1→ v2 的最短距离应该是 min{d11+d12 , d12+d22 , d13+d32 , d14+d42 , d15+d52 , d16+d62 , d17+d72 } 即 min{d1r+dr2}。 因此可以构造一个新的矩阵 D(1) ，令 D(1) 中每一个元素为： dij(1) =min{dir+drj} ，则矩阵 D(1) 给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离。 再构造矩阵 D(2) ， dij(2) =min{dir (1) +drj (1)} 。 依次类推构造矩阵 D(k) ， dij(k) =min{dir (k -1) +drj (k -1)} 计算停止的控制： p是图中顶点数。 该例中 k = 3 上述 D(2) 中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。 教材160页例5 §4．网络的最大流 一. 网络最大流的有关概念 1. 有向图与容量网络 图中每条边有规定指向的图称为有向图，有向图的边称为 弧，记作(vi , vj )，表示方向从点 vi 指向点 vj ，有向图是点与弧的集合，记作 D(V, A )。 弧(vi , vj )的最大通过能力，称为该弧的容量，记为c(vi , vj ) ，或简记为 cij 。 定义了弧容量的网络称为容量网络。 容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。 从发点到收点之间允许通过的最大流量称为最大流。 多个收(发)点的网络可以转换为只含一个收(发)点。 2. 流与可行流 流是指加在网络各条弧上的一组负载量，对加在弧(vi ,vj )上的负载量记作 f (vi , vj ) ，或简记作 fij ，若网络上所有的 fij =0，这个流称为零流。 以 v( f )表示网络中从 s→t 的流量，则 零流是可行流，求最大流就是求v( f )的最大值。 称网络上满足下述条件(1