《第六章 网络规划与网络分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第六章 网络规划与网络分析精选文档.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章第六章 网网络规划与网划与网络分分析析本讲稿第一页，共九十一页内内 容容 图与网络图与网络树树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流最小费用最大流案例：网络的中心与选址问题案例：网络的中心与选址问题习习 题题本讲稿第二页，共九十一页6.1 图与网络图与网络自自然然界界和和人人类类社社会会中中许许多多事事物物以以及及事事物物之之间间的的关关系系，都都可可以用点和线连接起来的图形来描述。以用点和线连接起来的图形来描述。例如例如用用点点表表示示城城市市，点点间间联联线线表表示示城城市市间间的的道道路路，就就可可描描述述城城市市间间的的交交通通，如如果果联联线线旁旁标标注
2、注城城市市间间的的距距离离网网络络图图中中称称为为权权，形形成成加加权权图图，就就称称为为网网络络图图，就就可可进进一一步步研研究究从从一一个个城城市市到到另另一一个个城城市市的的最最短短路路径径；或或者者标标上上单单位位运运价价，就就可可分析运费最小的运输方案。分析运费最小的运输方案。本讲稿第三页，共九十一页例6-1由点及不带箭头的连线所组成的图形。由点及不带箭头的连线所组成的图形。点的相对位置如何、点与点之间联线的长短曲点的相对位置如何、点与点之间联线的长短曲直，对反映对象之间的关系并不重要。直，对反映对象之间的关系并不重要。表示表示5个球队之间的赛事关系。个球队之间的赛事关系。点点a,b
3、,c,d,e,f-5个球队，个球队，两点的连接两点的连接-两球队之间的赛事关系。两球队之间的赛事关系。本讲稿第四页，共九十一页例例 6-2 由点及带箭头的连线所组成的图形。由点及带箭头的连线所组成的图形。图图 6-2 是一张管道运输网示意图是一张管道运输网示意图-城市间物资运输关系，城市间物资运输关系，v1,v2,v3,v4,v5,v6,v7-7个城市，个城市，箭箭线线旁旁的的数数字字-物物流流的的最最大大容容量量。现现在在要要求求出出从从v1地地到到v7地地的的可运送的最大流方案。可运送的最大流方案。边边-两点间不带箭头的连线两点间不带箭头的连线弧弧-带箭头的连线。带箭头的连线。本讲稿第五页
4、，共九十一页一、无向图一、无向图由点和边由点和边组成的图称为无向图，图组成的图称为无向图，图 6-3即为无向图即为无向图（1）无向图）无向图定义定义6-1 无向图无向图是一个无序二元组（是一个无序二元组（V，E），记为），记为G=（V,E），其中是），其中是p个点的集合，简称定点集；个点的集合，简称定点集；E=（e1，e2，eq）是是条条边边的的集集合合，简简称称边边集集合合，并并且且是是一个无序二元组，记为一个无序二元组，记为 。顶点数：点集顶点数：点集V中中元素的个数称为图元素的个数称为图G的顶点数，记为的顶点数，记为。如图。如图 6-3，本讲稿第六页，共九十一页为为的端点，的端点，为为的
5、关联边。的关联边。若点若点vi,vj有边相连，即有边相连，即，则称，则称vi,vj相邻，相邻，vi,vj与与e关联关联。v3,v5相邻，相邻，v3,v5与与e7关联关联。图图63。如图。如图 6-3，端点：对于边端点：对于边，称，称vi，vj为为e的端点。的端点。e为为vi,vj的关联边。的关联边。边数边数：边集：边集 E中元素的个数，记为中元素的个数，记为本讲稿第七页，共九十一页（2）简单图不含环和多重边的图称为简单图，含有多重边的图称为多重图。不含环和多重边的图称为简单图，含有多重边的图称为多重图。(3)点的次（度）点的次（度）以点以点v为为端点的边数叫做点端点的边数叫做点v的次，记作的次
6、，记作d(v)。如图如图6-3中中,d(v1)=4,d(v2)=4。若若，则称，则称称为图称为图G的次序列。的次序列。环（自回路）：一条边的两个端点如果相同，称此边为环。如环（自回路）：一条边的两个端点如果相同，称此边为环。如 图图6-3中的中的e1。多重边多重边：两个点之间多于一条边的，如图：两个点之间多于一条边的，如图6-3中的中的e4，e5.本讲稿第八页，共九十一页 次为次为 1 的点的点-悬挂点，连接悬挂点的边悬挂点，连接悬挂点的边-悬挂边。悬挂边。次为次为0的点的点-孤立点。孤立点。次为奇数的点次为奇数的点-奇点，次为偶数的点奇点，次为偶数的点-偶点。偶点。定定理理 6-1 任任何何
7、图图G=（V,E）中中，所所有有点点的的次次数数之之和和等等于于边边数数的的2倍。即倍。即 证证：由由于于每每条条边边必必有有两两个个顶顶点点关关联联，在在计计算算点点的的次次时时，每每条条边边均被计算了两次，所以顶点次数之和等于边数的均被计算了两次，所以顶点次数之和等于边数的2倍。倍。本讲稿第九页，共九十一页定理定理 6-2 任何图任何图G=（V,E）中，奇点的个数必为偶数。）中，奇点的个数必为偶数。证：设图证：设图 中奇点与偶点的集合分别为中奇点与偶点的集合分别为V1和和V2，由定理由定理 6-1 知知由于由于2q(G)为偶数，而为偶数，而 是若干个偶数之和，也是若干个偶数之和，也为偶数。
8、所以为偶数。所以 必为偶数，即奇点的个数必为偶数，即奇点的个数 必必为偶数。为偶数。本讲稿第十页，共九十一页（4）链）链 链：链：对于无向图对于无向图G=（V,E）,称顶点和边交替的序列称顶点和边交替的序列 为连接为连接和和的一条链，简记为的一条链，简记为。其中。其中-链的两个端点。链的两个端点。-是链。是链。和和两个端点重合的链，称为圈。在一个图中，如果任何两个顶点之两个端点重合的链，称为圈。在一个图中，如果任何两个顶点之间都有一条链，该图称为连通图。间都有一条链，该图称为连通图。本讲稿第十一页，共九十一页二、有向图二、有向图（1）有向图）有向图 有向图是一个有序二元组有向图是一个有序二元组
9、（V,A），记为），记为D（V,A），其中），其中是是p个顶点的集合，个顶点的集合，是是q条弧条弧的集合，并且的集合，并且是一个有序二元组，记为是一个有序二元组，记为并称并称 是以是以vi为始点，为始点，vj为终点的弧，为终点的弧，i，j的顺序不能颠倒，的顺序不能颠倒，弧的方向弧的方向-箭头标识。箭头标识。由点和弧组成的图称为有向图由点和弧组成的图称为有向图本讲稿第十二页，共九十一页（2）简单有向图）简单有向图 两个端点重合的弧称环。如图两个端点重合的弧称环。如图 6-4 中的中的a1.图图6-4两个端点之间的同向弧数大于等于两个端点之间的同向弧数大于等于2，称为多重弧。，称为多重弧。无环也无
10、多重弧的有向图称为简单有向图。无环也无多重弧的有向图称为简单有向图。本讲稿第十三页，共九十一页（3）点的出次和入次）点的出次和入次以点以点v为起点的弧数叫做点为起点的弧数叫做点v的出次，记作的出次，记作以点以点v为终点的弧数叫做点为终点的弧数叫做点v的入次，记作的入次，记作 称称 为点为点v的次。的次。（4）路）路 在有向图在有向图D=(V,A)中，点和弧交替的序列中，点和弧交替的序列，若有，若有或或，则称，则称P是一条链接是一条链接和和的有向路。的有向路。本讲稿第十四页，共九十一页三、网络三、网络 实实际际问问题题中中，往往往往只只用用图图来来描描述述所所研研究究对对象象之之间间的的关关系系
11、还还不不够够，如如果果在在图图中中赋赋予予边边一一定定的的数数量量指指标标，我我们们常常称称之之为为“权权”。依依据据研研究究问问题题的的需需要要，权权可可以以代代表表距距离离，也也可可以以代代表表时时间间、费用、容量、可靠性等。通常把这种费用、容量、可靠性等。通常把这种赋权图称为网络赋权图称为网络。与与无无向向图图和和有有向向图图相相对对应应，网网络络又又分分为为无无向向网网络络和和有有向向网络。网络。本讲稿第十五页，共九十一页图的矩阵表示方法：，其中，其中 则称则称A为为G的的关关联矩阵联矩阵。关联指顶点与边的关系。关联指顶点与边的关系。关联矩阵：在图关联矩阵：在图G=(V,E)中，中，V
12、=(v1,v2,vp),E=(e1,e2,eq),构造一个矩阵构造一个矩阵本讲稿第十六页，共九十一页，其中，其中 则称则称A为为G的邻接的邻接矩阵。邻接指顶点与顶点的关系。矩阵。邻接指顶点与顶点的关系。邻接矩阵：邻接矩阵：在图在图G=(V,E)中，中，V=（v1,v2,vp),E=(e1,e2,eq),构造一个矩阵构造一个矩阵本讲稿第十七页，共九十一页权矩阵权矩阵：在图在图G=(V,E)中，中，V=(v1,v2,vp),E=(e1,e2,eq),其边其边vi,vj有权有权wij。构造一个矩阵。构造一个矩阵 ，其中，其中则则称称A为为G的权的权矩阵。矩阵。本讲稿第十八页，共九十一页6.2 6.2
13、 树树a）b）实例：已知有实例：已知有 5个城市，要在它们之间架设电话线网，要求任何两个城个城市，要在它们之间架设电话线网，要求任何两个城市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。满足要求的电话网必须是：满足要求的电话网必须是：连通的；连通的；不含圈的。满足这两点要求的图称为不含圈的。满足这两点要求的图称为“树树”。本讲稿第十九页，共九十一页6.2.1 6.2.1 树的基本概念与性质树的基本概念与性质定义定义：连通且不含圈的无向图称为树。树中次为：连通且不含圈的无向图称为树。树中次为1的顶点称为树叶的顶点称为树叶(悬
14、挂悬挂点点)，次大于，次大于 1的顶点称为分枝点。的顶点称为分枝点。树的性质可用下面定理给出：树的性质可用下面定理给出：设有图设有图G=(V,E)，n和和m分别为图分别为图G的顶点数和边数，则下列命题是的顶点数和边数，则下列命题是等价的：等价的：（1）G是一个树。是一个树。（2）G无圈，且无圈，且m=n-1。（3）G连通，且连通，且m=n-1。（4）G无圈，但每加一条新边即存在唯一一个圈。无圈，但每加一条新边即存在唯一一个圈。（5）G 连通，但每舍去一条边就变成不连通。连通，但每舍去一条边就变成不连通。（6）G中任意两点，有唯一路相连。中任意两点，有唯一路相连。本讲稿第二十页，共九十一页定义定
15、义6-7 图图G=(V,E)，若，若E是是E的子集，的子集，是是V的子集，且的子集，且中的边仅与中的边仅与中的顶点相关联，则称中的顶点相关联，则称是是的一个子图。特别地，若的一个子图。特别地，若，则，则称为称为子图（或支撑子图）。子图（或支撑子图）。的生成的生成定义定义6-8 若图若图G的生成子图是一棵树，则称该树为的生成子图是一棵树，则称该树为G的生成树，的生成树，或简称为图或简称为图G的树。的树。图图G中属于生成树的边称为树枝，不在生成树中的边称为弦。中属于生成树的边称为树枝，不在生成树中的边称为弦。本讲稿第二十一页，共九十一页定理定理 6-4 图图G=(V,E)有生成树的充分必要条件为有
16、生成树的充分必要条件为 G是连通图是连通图。证明：必要性由定义直接可得。证明：必要性由定义直接可得。充充分分性性的的证证明明过过程程如如下下：设设图图G是是连连通通的的。若若G不不含含圈圈，则则 G就就是是其其自自身身的的一一棵棵生生成成树树；若若G含含有有圈圈，任任取取一一个个圈圈，从从圈圈中中任任意意去去掉掉一一条条边边，得得到到图图G的的一一个个生生成成子子图图G1。如如果果G1不不含含圈圈，那那么么G1是是G的的一一棵棵生生成成树树；如如果果G1仍仍含含有有圈圈，那那么么从从G1中中任任取取一一个个圈圈，从从圈圈中中再再任任意意去去掉掉一一条条边边，得得到到图图 G的的一一个个生生成成
17、子子图图G2。重重复复使使用用此此法法使使每每个个圈圈都都受受到到破破坏坏，最最后后可可以以得得到到G的的一一个个生生成成子子图图Gk，它它是是不不含含圈圈的生成子图。这就是的生成子图。这就是G一棵生成树。一棵生成树。本讲稿第二十二页，共九十一页6.2.2 最小支撑树及其算法最小支撑树及其算法（1）构造支撑树的算法）构造支撑树的算法 1)破圈法破圈法 破圈法思路：任取一圈，从圈中去掉任一条边，再对余下的圈重复相同的步骤，直到图中所有的圈破掉为止。本讲稿第二十三页，共九十一页 2）避圈法）避圈法 避圈法思路：将不连通的无圈图通过边的增加，逐步变成连避圈法思路：将不连通的无圈图通过边的增加，逐步变
18、成连 通无圈图。通无圈图。避圈法步骤：避圈法步骤：为连通图。为连通图。步骤步骤1 始取始取 ；步步骤骤 2 若若Gk 连连通通，则则Gk为为支支撑撑树树；若若Gk不不连连通通，任任选选图图G边边集集E中中的的一一边边e，使使e的的两两个个端端点点分分属属两两个个不不同同的的连连通通分分图图，得得，；步骤步骤 3 若若 ，则重复步骤，则重复步骤 2；否则，；否则，Gk一定是支撑树。一定是支撑树。本讲稿第二十四页，共九十一页 将支撑树的构造与边权的选择结合，产生最小树的概念。将支撑树的构造与边权的选择结合，产生最小树的概念。（2）最小支撑树定义）最小支撑树定义 设设有有一一个个连连通通图图G=(V
19、,E),每每一一边边e=vi,vj有有一一个个权权w(e)=wij，如如果果是的一个支撑树，称中所有边的权之和为支撑树的权，记为：是的一个支撑树，称中所有边的权之和为支撑树的权，记为：如如果果支支撑撑树树T*的的权权W(T*)是是G的的所所有有支支撑撑树树中中权权数数最最小小的的，则则称称T*是是G的最小支撑树（也称最小树），即的最小支撑树（也称最小树），即本讲稿第二十五页，共九十一页（3）寻找最小支撑树的算法）寻找最小支撑树的算法 寻寻找找最最小小支支撑撑树树也也可可以以用用上上面面介介绍绍的的破破圈圈法法和和避避圈圈法法，但但要要在在舍舍边边和增边时，增加一些边的权数的限制。和增边时，增加
20、一些边的权数的限制。1）破圈法）破圈法 步骤：步骤：从图从图G中任取一圈，去掉这个圈中权数最大的一条边，得一中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图支撑子图G1。在。在G1中再任取一圈，再去掉圈中权数最大的一条边，中再任取一圈，再去掉圈中权数最大的一条边，得得G2。如此继续下去，一直到剩下的子图中不再含圈为止。如此继续下去，一直到剩下的子图中不再含圈为止。该子图该子图G1就是的最小支撑树就是的最小支撑树T*。本讲稿第二十六页，共九十一页2）Kruskal算法（避圈法）算法（避圈法）1956年年 基本思想基本思想-每次将一条权最小的弧加入子图每次将一条权最小的弧加入子图T 中，中，
21、并保证不形成圈。即按照边长由小到大排序，如果当并保证不形成圈。即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧。当弧有前弧加入后不形成圈，则加入这条弧。当弧有n-1条条 时，即为最小树。时，即为最小树。本讲稿第二十七页，共九十一页例例6-4 用用Kruskal算法求解下图算法求解下图(6-8)所示网络的最小树，每所示网络的最小树，每 条边上的数表示该边的权值。条边上的数表示该边的权值。本讲稿第二十八页，共九十一页3）Prim算法算法(边割法边割法)1957年年核核心心思思想想-不不断断扩扩展展一一个个子子树树，使使其其逐逐步步包包含含所所有有的顶点。的顶点。具具体体增增边边的的选
22、选择择，是是在在当当前前子子树树的的顶顶点点集集合合与与补补集集合合所形成的边割中选择最小的边。所形成的边割中选择最小的边。Prim算算法法是是一一个个子子树树逐逐步步扩扩张张的的过过程程，Kruskal算算法是多个子树逐步融合的过程。法是多个子树逐步融合的过程。本讲稿第二十九页，共九十一页Prim算法：算法：步骤步骤0 从图中任选一点从图中任选一点vi，让，让viS，图中其余点均包含在，图中其余点均包含在 中；中；步骤步骤2 从从S和和 之间的连线中找出最小边，这条边一定包含在之间的连线中找出最小边，这条边一定包含在 最小支撑树内，不妨设最小边为最小支撑树内，不妨设最小边为vi,vj，将，将
23、vi,vj标记成标记成 最小支撑树内的边；最小支撑树内的边；步骤步骤3 令令 ，；步骤步骤4 重复步骤重复步骤2、步骤、步骤3，一直到图中所有点均包含在，一直到图中所有点均包含在S中中 为止。为止。本讲稿第三十页，共九十一页例题例题6-5 用用Prim算法求解图算法求解图69（a）中的最小树。）中的最小树。本讲稿第三十一页，共九十一页解：求解结果见图解：求解结果见图69（b）本讲稿第三十二页，共九十一页 例例6-在在一一个个地地区区有有一一个个公公共共服服务务机机构构，如如飞飞机机场场、医医院院等等，图图610中中O所所示示。三三个个乡乡镇镇（图图6-10中中的的v1,v2,v3所所示示）需需
24、要要连连接接到到这这个个公公共共服服务务机机构构。乡乡镇镇与与服服务务机机构构之之间间、乡乡镇镇与与乡乡镇镇之之间间的的连连接接高高速速公公路路的的造造价价为为边边的的权权。问问如如何何构构建建这这个个连连接接网网络络并分配建设费用？并分配建设费用？本讲稿第三十三页，共九十一页解：是一个最小支撑树的构建和建设成本分担问题。解：是一个最小支撑树的构建和建设成本分担问题。将将v1,v2,v3分别连接到分别连接到O的建设成本为的建设成本为 C(v1)9，C(v2)10，C(v3)11；将将 v1,v2 连接到连接到O的最小树的建设成本为的最小树的建设成本为C(v1,v2)17，同样，同样，C(v1,
25、v3)18，C(v2,v3)11；将将3个顶点连接到个顶点连接到 的最小树的最小树O的建设成本的建设成本C(v1,v2,v3)18。设分别承担的建设费用为设分别承担的建设费用为x1,x2,x3，则建设费用的分配应该满足：，则建设费用的分配应该满足：有有无无限限个个向向量量满满足足上上式式，每每个个向向量量都都可可以以作作为为一一个个建建设设费用的分配方案。费用的分配方案。本讲稿第三十四页，共九十一页6.3 最短路问题最短路问题 优化问题优化问题-如设备更新、管道铺设、线路安排、如设备更新、管道铺设、线路安排、厂区布局等。厂区布局等。曾介绍动态规划解法，但某些最短路问题（如道曾介绍动态规划解法，
26、但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，路不能整齐分段者）构造动态规划方程比较困难，而图论方法则比较有效。另外，这个问题相对比而图论方法则比较有效。另外，这个问题相对比较简单，其算法经常做为其他问题的子算法而调较简单，其算法经常做为其他问题的子算法而调用。用。本讲稿第三十五页，共九十一页6.3.1 基本概念与基本概念与Bellman方程方程 最最短短路路问问题题-设设N=(V,A,W)为为网网络络图图，图图中中各各边边(vi,vj)有有权权wij（wij=表表示示vi,vj之之间间没没有有边边），v1为为起起始始点点，vj为为图图中中任任意意一一点点。网网络络中中有有
27、多多条条v1vj的的路路P,每每条条路路的的权权是是其其所所有有构构成成弧弧的的权之和。权之和。求求一一条条v1vj的的路路 ，使使它它是是从从v1到到vj的的所所有有路路中中总总权权最最小小的的路。即：优化问题路。即：优化问题本讲稿第三十六页，共九十一页 对对于于网网络络中中的的一一个个圈圈，其其权权是是其其所所构构成成边边的的权权之之和和。权权为为正的圈正的圈-正圈；正圈；权为负的圈权为负的圈-负圈；负圈；权为权为0的圈的圈-零圈。零圈。本讲稿第三十七页，共九十一页令令uj表表示示网网络络中中v1vj的的最最短短路路的的长长度度。基基于于动动态态规规划划中中递递归归方方程的思想，得到求解最
28、短路问题的递归关系如下：程的思想，得到求解最短路问题的递归关系如下：定定理理 6-5 设设有有向向网网络络G中中只只含含正正圈圈，并并且且从从点点v1到到其其余余点点 vj都都有有有限长度的有向路，那么有限长度的有向路，那么(6.1)有唯一有限解。有唯一有限解。本讲稿第三十八页，共九十一页定定理理 6-6 设设N=(V,A)不不含含圈圈，则则N的的顶顶点点可可以以重重新新编号，使编号，使 。3例例5.1-最短路径问题V1V8V7V5V4V3V9V10V212353313424135215V63本讲稿第三十九页，共九十一页例例6-7 计算如下网络中计算如下网络中v1到到 各点的最短路。各点的最短
29、路。解：这是一个有圈网络图，但解：这是一个有圈网络图，但v1是起始点，故进入是起始点，故进入v1的弧可以删去。的弧可以删去。对顶点进行重新标号，得到网络图，图对顶点进行重新标号，得到网络图，图6-11(b)。本讲稿第四十页，共九十一页Bellman方程的计算：方程的计算：按照按照ui，求出最短路网络，图，求出最短路网络，图6-11(c)。本讲稿第四十一页，共九十一页6.3.2 Dijkstra算法算法(wij0)-1959年 双标号法双标号法-图中的每个点图中的每个点vj 赋予两个参数（标号）赋予两个参数（标号）uj-从起点从起点v1到到vj的最短路的长度，是距离标号；的最短路的长度，是距离标
30、号；-前前趋趋标标号号，是是记记录录在在v1到到vj的的最最短短路路上上，vj 前前面面一一个个邻邻点点的的下下标标，用用来来标标识识最最短短路路路路径径，从从而而可可对对终终点点到到始始点点进进行反向追踪，找到行反向追踪，找到v1到到vj的最短路。的最短路。通过不断修改这些标号，进行迭代计算。通过不断修改这些标号，进行迭代计算。本讲稿第四十二页，共九十一页Dijkstra 算法：步骤步骤 0 给起点给起点v1标号标号(0,s)，表示从，表示从v1到到v1的距离为的距离为0，v1为起为起 点。点。步骤步骤1 如果如果S=V，则，则uj即为即为v1到到vj的最短路的长度，最短路可的最短路的长度，
31、最短路可 以按照以按照 pred(j)记录的信息，反向追踪即可获得，结束。记录的信息，反向追踪即可获得，结束。否则，转步骤否则，转步骤2。步骤步骤2 求出弧集求出弧集 。若。若 ，表明从，表明从 所有已经赋予标号的顶点出发，不再有这样的弧，它所有已经赋予标号的顶点出发，不再有这样的弧，它 的另一顶点尚未标号，则计算结束。对于已有标号的顶的另一顶点尚未标号，则计算结束。对于已有标号的顶 点，可求得从到达这个顶点的最短路，对于没有标号的点，可求得从到达这个顶点的最短路，对于没有标号的 顶点，则不存在从顶点，则不存在从v1到达这个顶点的路。到达这个顶点的路。若弧集，若弧集，转步骤转步骤3。本讲稿第四
32、十三页，共九十一页 步骤步骤3 对弧集对弧集A中的每一条弧中的每一条弧(vi,vj)，计算，计算 。则则vi 赋予双标号赋予双标号 ，其中，其中 。转步骤。转步骤 2 经经上上述述一一个个循循环环的的计计算算，将将求求出出v1到到一一个个顶顶点点vj的的最最短短路路及及其长度，从而使一个顶点其长度，从而使一个顶点vj得到双标号。得到双标号。若有若有n个顶点，则最多计算个顶点，则最多计算(n-1)循环，即得最后结果。循环，即得最后结果。本讲稿第四十四页，共九十一页例例6-8 求求v1到其余各点的最短路到其余各点的最短路 本讲稿第四十五页，共九十一页 至此，自顶点至此，自顶点1至其余顶点的最短路都
33、已求得。如下图粗线示至其余顶点的最短路都已求得。如下图粗线示 标号法是一种按标号值从小到大的逐步外探法。标号法是一种按标号值从小到大的逐步外探法。本讲稿第四十六页，共九十一页补充补充(wij不全0，存在wij0)。抹掉图上所有标号，重复抹掉图上所有标号，重复 步骤步骤 2-步骤步骤 3。本讲稿第七十二页，共九十一页步步骤骤 4 写写出出最最小小截截集集 和和最最大大流流 的的流流量量 ，终止计算，终止计算。例例6-10 试试用用 FordFulkerson 标标号号法法求求图图 618所所示示的的网网络络最最大大流，括号中，第一个数字是容量，第二个数字是容量。流，括号中，第一个数字是容量，第二
34、个数字是容量。本讲稿第七十三页，共九十一页本讲稿第七十四页，共九十一页本讲稿第七十五页，共九十一页本讲稿第七十六页，共九十一页本讲稿第七十七页，共九十一页图图 619本讲稿第七十八页，共九十一页6.5 最小费用最大流最小费用最大流 在在上上节节最最大大流流问问题题中中，每每一一个个可可行行流流在在现现实实生生活活中中，还还对对应应着着一一定定的的费费用用，许许多多情情况况下下优优化化目目标标不不但但要要求求流流量量尽尽可可能能的的大大，还还要要求求费费用用尽尽可可能能的的小小。在在一一个个网网络络中中每每条条弧弧都都有有“容容量量”和和“费费用用”两两个个限限制制的的条条件件下下，寻寻求求vs
35、到到 vt 的的最最大大流流，使使该该最大流在所有最大流中费用达到最小。最大流在所有最大流中费用达到最小。本讲稿第七十九页，共九十一页 给给出出网网络络D=(V,A,C,B)，其其中中C是是容容量量，B是是费费用用，即即对对于于每每条条弧弧，有有容容量量cij0，有有费费用用bij0。对对于于D的的一一个个可可行行流流 ，定义其，定义其费用费用为为 求求解解最最小小费费用用最最大大流流问问题题的的基基本本思思想想是是在在寻寻求求最最大大流流的的算算法法过过程程中中，不不但但通通过过增增广广链链使使流流量量逐逐步步增增加加，还还要要考考虑虑费费用用的的约约束束，即每次可行流的调整都使费用增加最小
36、。即每次可行流的调整都使费用增加最小。本讲稿第八十页，共九十一页当当沿沿着着可可行行流流 f 的的一一条条的的增增广广链链，以以调调整整 f，得得到到新新的的可可行行流流 f 时，时，b(f)比比 b(f)增加：增加：1时，费用的增加量是时，费用的增加量是 这这个个数数值值反反映映了了增增广广链链的的好好坏坏，这这个个数数值值越越小小，这这条条增增广广链链就就越越好。好。本讲稿第八十一页，共九十一页 把把 称为增广链称为增广链的费用。的费用。若若 f 是流值为是流值为v(f)的所有可行流中费用最小者，而的所有可行流中费用最小者，而 是关于是关于 f 的费用最小的增广链，那么沿的费用最小的增广链
37、，那么沿去调整可行流去调整可行流 f，得到可行流，得到可行流 f，新可行流就是流值为新可行流就是流值为v(f)的所有可行流中费用最小的可行的所有可行流中费用最小的可行流。流。确确定定一一个个最最小小费费用用可可行行流流,然然后后找找出出最最小小费费用用增增广广链链，按按照照最最小小费费用用增增广广链链对对可可行行流流进进行行调调整整，一一直直调调整整下下去去，直直到到找找不不出出增广链为止，这样得到的可行流即为最小费用最大流。增广链为止，这样得到的可行流即为最小费用最大流。本讲稿第八十二页，共九十一页 为为了了寻寻找找最最小小费费用用增增广广链链，我我们们以以原原可可行行流流 f 为为基基础础
38、，构构造造一一个个新新赋赋权权图图D(f)=(V,A(f),W)。D(f)的的顶顶点点为为原原网网络络D的的顶顶点点V，把把D中中的的每每条条弧弧A变变为为两两条条方方向向相相反反的的两两条条弧弧，,形成弧集合形成弧集合 A(f),。弧的赋权原则如下：。弧的赋权原则如下：对于弧对于弧，有，有 对于弧对于弧,有有本讲稿第八十三页，共九十一页最小费用最大流的算法：最小费用最大流的算法：（1）取零流为初始最小费用可行流，记为）取零流为初始最小费用可行流，记为f(0)。（2)若若第第k步步得得到到最最小小费费用用可可行行流流f(k),则则构构造造一一个个新新赋赋权权图图D(f(k),在在D(f(k)中
39、中寻寻求求从从vsvt 最最短短路路。若若不不存存在在最最短短路路，则则目目前前的的可可行行流流F(k)即即为为网网络络D的的最最小小费费用用最最大大流流；若若存存在在最最短短路路，则则在在原原网网络络D中中得得到到了了相相应应的的最最小小费费用用增增广广链链，对对F(k)进进行行调调整整，调整量为调整量为本讲稿第八十四页，共九十一页（3）调整方法如下：）调整方法如下：重复进行上述步骤，直到找不出增广链为止。重复进行上述步骤，直到找不出增广链为止。本讲稿第八十五页，共九十一页本讲稿第八十六页，共九十一页本讲稿第八十七页，共九十一页 D(f(0)中中最最短短路路见见图图6-22中中的的粗粗线线所
40、所示示，由由此此找找到到最最小小费费用用增增广广链，见图链，见图6-21中粗线所示。中粗线所示。利用最小费用增广链对可行流进行调整，调整后的新流见图利用最小费用增广链对可行流进行调整，调整后的新流见图6-23。（2）继续进行可行流的调整：）继续进行可行流的调整：本讲稿第八十八页，共九十一页 图图6-24中中的的最最短短路路见见粗粗线线所所示示，因因此此找找到到最最小小费费用用增增广广链链，见见图图6-23中中粗粗线线所所示示。利利用用最最小小费费用用增增广广链链对对可可行行流流进进行行调调整整，调调整整后后的的新新流流见见图图6-25。本讲稿第八十九页，共九十一页本讲稿第九十页，共九十一页 上上图图已已经经找找不不出出 的的路路，因因此此也也没没增增广广链链了了，即即图图6-25所所示示的的可可行行流流即即为为最最小小费费用用最最大大流流，流流值值v(f)5，其费用为，其费用为31。本讲稿第九十一页，共九十一页