《八图与网络研究》由会员分享，可在线阅读，更多相关《八图与网络研究（110页珍藏版）》请在金锄头文库上搜索。
1、第八章 图与网络分析 最短路问题 网络最大流问题 最小费用最大流问题 第八章 图与网络分析 最短路问题 网络最大流问题 最小费用最大流问题 什么是最短路问题？什么是最短路问题？ 固定起点的最短路 DijkstraDijkstra( (狄克斯拉狄克斯拉) () (荷兰荷兰) )算法：标号法算法：标号法 逐次逼近算法逐次逼近算法(Ford(Ford(美国美国) )算法算法) )：修正标号法：修正标号法 每 对 顶 点 之 间 的 最 短 路 Floyd(Floyd(佛洛伊德佛洛伊德) )算法算法 最短路问题 最短路问题提出 在现实生活中，除公路运输网络、电讯网络 等网络图以外，还有输油管线这样的图
2、。在输油 管线图中，为反映油的输送情况，两点间不仅有 连线，线上往往还标有箭头，以表示油的流动方 向。又如，指挥系统图、控制系统图等图中都标 有指向。从这样的一类图中就可以概括为有向图 的概念。 有向网络与混合图 如果在图D=（V，A）中，给每一弧赋予权值，如 将弧aij=(vi,vj)有权值 wij，记为w(aij)=wij则赋 权有向图D=（V，A）称为有向网络，在不至于混 淆时，也简称网络。 混合图如果一个图中既有边，也有弧，那么称这 种图为混合图。它往往出现在既有单行线，又有 双行线的交通图中。 1 2 5 3 4 3 7 2 最短路问题引例 下图为单行线交通网，每弧旁的数字表示通过这
3、条线 所需的费用。现在某人要从v1出发，通过这个交通网 到v8去，求使总费用最小的旅行路线。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 12 10 6 1 2 10 v8 v9 v7 2 36 3 从v1到v8： P1=（v1，v2，v5，v8） 费用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= 从v1到v8的旅行路线 从v1到v8的路。 旅行路线总费用 路上所有弧权之和。 最短路问题中，不考虑有向环、并行弧。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 12 10 6 1 2 10 v8 v9 v7
4、 2 36 3 几个概念 路：设p是D中一个首尾相连的弧的集合，如果vs是 它的第一条弧的始点，vt是它的最后一条弧的终 点，则称它是以点vi为始点，以点vt为终点的一 条路。 路长：路p中所有弧的权值的和称为路p的长，记为 设图D=（V，A）是一有向网络 v2 v5 2 3 4 6 4 v3 v1 V4 v6 12 10 6 1 2 10 v8 v9 v7 2 36 3 设P是以点vs为始点，以点vt为终点的所有路的集合， 如果 ,且 ，则称p0是以点vs 为始点，以点vt为终点的最短路。而称其路长为点 vs到点vt的距离，记为 。 几个概念 注意：在有向网络中,一般 最短路及一点到另一点的
5、距离 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 求解最短路问题的Dijkstra算法 条件：当所有 wij 0 时，用来求给定点vs到任一 个点vj 最短路的公认的最好方法。 事实：如果P是D中从vs到vj的最短路，vi是P中的一 基解 个点，那么，从vs沿P到vi的路是从vs到 vi的最 基解 短路。 Dijkstra算法是Dijkstra在1959年提出的，可用于求解 指定两点间的最短路问题，或从指定点到其余各点的最短 路问题。由于其以标号为主要特征，又称为标号法。 v1 v2 v3 v4 v5
6、最短路的子路是最短路 Dijkstra算法 （1 1）求解思路）求解思路从始点出发，逐步顺序地 向外探寻，每向外延伸一步都要求是最短的。最短的。 （2 2）使用条件）使用条件网络中所有的弧权均 非负非负，即 。 1.标号 P（固定标号或永久性标号） 从始点到该标号点的最短路权ui 。 2.标号 T（临时性标号） 从始点到该标号点的最短路权上界上界ui 。 选用符号的意义 P(i, ui) 3.前点标号i 表示点vs到vj的最短路上vj的前一点前一点。 T(i, ui) Dijkstra算法步骤算法步骤： 第二步：第二步：考虑满足条件考虑满足条件 的所有点；的所有点； v v j j 具有具有T
7、 T 标号标号; ; 修改修改 v v j j 的的T T标号为标号为 ， 并将结果仍记为并将结果仍记为T(T( v vj j) ) 第一步：第一步：始点标上固定标号始点标上固定标号 , ,其余各其余各 点标临时性标号点标临时性标号 T T ( (v v j j )=)= , j, j 1;1; 第三步：第三步：若网络图中已无若网络图中已无 T T 标号点，停止计算。标号点，停止计算。 否则否则, , 令令 ， s s 为为 T T 标号点集标号点集, , 然后然后将将 的的T T 标号改成标号改成P P 标号标号 ，转入第二步。，转入第二步。 1,6 图上标号法 v5 v2 2 3 4 6
8、4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,3 1, 1, 1, 1,11,1 永久标号永久标号 临时标号 1,6 图上标号法 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, 1,1 1, 1,3 1, 1, 1, 0,0 1,14,11 1,3 永久标号 临时标号 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,1 1, 1, 1, 1,3
9、图上标号法 4,11 1,3 1,63,53,5 永久标号 临时标号 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 图上标号法 3,5 2, 62, 6 永久标号 临时标号 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1,3 5,12 5,95,9 图上标号法 3,5 2, 6 永久标号 临时标号 v5 v2 2 3 4 6 4 v3 v1 v4
10、 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, 5, 12 1,3 5,9 5, 12 3,5 2, 6 图上标号法 永久标号 临时标号 4,11 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 4,11 0,0 1,1 1, 1,3 5, 12 3,5 2, 6 图上标号法 5,9 永久标号 临时标号 标号结束 反向追踪 例 求如下交通网络中各对点间最短路路长。 Dijkstra算法（标号法）算法（标号法）算例 3 10 2 5 v4 v1v2 v5 v3 1 22
11、 6 2 4 4 8 混合图 无向网络: 负权弧时。 wij vivj wij wij vjvi无向网络中，最短路最短链。 多个点对之间最短路？ v1v2 v3 1 2 -3 Dijkstra算法失效 Dijkstra算法注意的问题 逐步逼近算法 路矩阵算法 5 7 2 7 4 6 1 2 6 3 2 0 2 6 5 7 7 10 v3 v1 v2 v4 v5 v6 v7 练习：求如下无向网络中v1到v7的最短路 Dijkstra算法求最短链 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 逐次逼近算法 计
12、算指定点v1到其余各点的最短路时，某些 问题会出现有负权弧的图,如： 此时Dijkstra算法（标号法）有可能失效。 逐次逼近法对于这类问题的解决很有帮助。 v1v2 v3 1 2 -3 逐次逼近算法思想 该公式表明，P(1)1j中的第j个分量等于P(0)1j的分量与基 本表中第j列相应元素路长的最小值，它相当于在点v1与vj 之间插入一个转接点（v1,v2,vn中的任一个，含点v1与 vj）后所有可能路中的最短路的路长；每迭代一次，就相 当于增加一个转接点，而P(k)1j中的每一个分量则随着k的增 加呈不增的趋势，直到出现稳定。 用于计算指定点v1到其余各点的最短路 j=1,2,n. k=1
13、,2,tn. 2.计算 逐次逼近算法基本步骤 j=1,2,n. 1.令 其元素既是v1到vj的最短路长。 3.当出现 时， 例 计算从点v1到所有其它顶点的最短路 解：初始条件为 以后按照公式 进行迭代。 直到得到 ，迭代停止。 v1 v2 v3 v4 v6 v5 v8 v7 2 -3 5 4 6 7 -2 4 -3 3 4 2 -1 v1 v2 v3 v4 v5 v6 v7 v8 v8v7v6v5v4v3v2v1 wij v1 v2 v3 v4 v6 v5 v8 v7 2 -3 5 4 6 7 -2 4 -3 3 4 2 -1 4 0 0 -1 6 0 2 4 0 -3 3 -3 0 7 5
14、 -2 0 4 2 0 0 利用下 标追踪 路径 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 某些问题需要求网络上任意两点间的最 短路。当然，它也可以用标号算法依次改变 始点的办法来计算，但是比较麻烦。 这里介绍Floyd在1962年提出的路矩阵法 ，它可直接求出网络中任意两点间的最短路 。 Floyd算法(路矩阵法)思想 网络D=（V，A，W），令U=(dij)nn， 表示D中vi到vj的最 短路的长度。 考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉， 得只剩vi，vj的一个子网络D0
15、，记 wij为弧（ vi，vj）的权。 在D0中加入v1及D中与vi，vj，v1相关联的弧， 得D1，D1中vi到vj的最短路记为 ,则一定有 vivj v1 wij Floyd算法(路矩阵法)思想 再在D1中加入v2及D中与vi，vj，v1， v2相关联的弧，得D2 ，D2中vi到vj的最短路长记为 ，则有 随着转接点的逐步增加,我们会发现 二指定点间路的条数也会随之增加，但是其最短 路及路长可以确定； 当V中所有的点都可以作为转接点时，指定点vi 到vj间所有路中的最短路自然是图中指定点vi到vj间 的最短路。 Floyd算法(路矩阵法)思想 Floyd算法(路矩阵法)步骤 设有有向网络D=（V，A），其权矩阵为A=(aij)nn， 如下构造路矩阵序列： 则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。 1. 令权矩阵A为初始路矩阵D（0），即令D（0）=A 2. 依次计算K阶路矩阵D（K）=（d(k)ij）nn, k=1,2,n， 这里 路矩阵序列的含义 K阶路矩阵D（K
