图与网络优化课件.ppt
65页
湖州师范学院商学院湖州师范学院商学院运筹学运筹学（（operations research, OR）） 第八讲第八讲 图与网络优化图与网络优化商学院电子商务系商学院电子商务系9/21/20241 湖州师范学院商学院湖州师范学院商学院第八讲第八讲 图与网络优化图与网络优化一一. 图与树图与树二二. 最短路问题最短路问题 三三. 最大流问题最大流问题9/21/20242 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化 人们为反映一些对象之间关系时，常会用示意图人们为反映一些对象之间关系时，常会用示意图图的相关概念图的相关概念铁路交通图铁路交通图比赛情况图比赛情况图药品存放图药品存放图9/21/20243 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化 图是由一些点及一些点之间的连线图是由一些点及一些点之间的连线( (不带箭头或带箭头不带箭头或带箭头) )组组成的图形成的图形图的相关概念图的相关概念 两点之间不带箭头的连线称为边，带箭头的连线称为弧。
两点之间不带箭头的连线称为边，带箭头的连线称为弧 如果一个图如果一个图G G由点及边所构成，则称之为无向图由点及边所构成，则称之为无向图( (也简称为也简称为图图) )，记为，记为G=G=（（V V，，E E），式中），式中V V，，E E分别是分别是G G的点集合和边集合一的点集合和边集合一条连结点条连结点V Vi i，，V Vj j的边记为的边记为[ [V Vi i，，V Vj j] ]( (或或 [ [V Vj j，，V Vi i])]) 如果一个图如果一个图D D由点及弧所构成，则称为有向图，记为由点及弧所构成，则称为有向图，记为D=(VD=(V，，A)A)，式中，式中V V，，A A分别表示分别表示D D的点集合和弧集合一条方向是从的点集合和弧集合一条方向是从v vi i指指向向v vj j的弧，记为的弧，记为(v(vi i,v,vj j).).9/21/20244 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化点的集合：点的集合：无向图例子无向图例子边的集合：边的集合：9/21/20245 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化有向图例子有向图例子9/21/20246 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念 图图G G或或D D中的点数记为中的点数记为p(G)p(G)或或p(D)p(D)，边，边( (弧弧) )数记为数记为q(G)(q(D))q(G)(q(D))，分别简记为，分别简记为p p，，q q。
若边若边e =e =［［u u，，v v］］∈E∈E，则称，则称u u，，v v是是e e的端点，也称的端点，也称u u，，v v是相邻的称是相邻的称e e是点是点u(u(及点及点v)v)的关连边的关连边 若图若图G G中，某个边中，某个边e e的两个端点相同，则称的两个端点相同，则称e e是环是环( (如前图中的如前图中的e e7 7) ) 若两个点之间有多于一条的边，称这些边为多重若两个点之间有多于一条的边，称这些边为多重边边( (如前图中的如前图中的e e1 1,e,e2 2) )9/21/20247 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念 一个无环，无多重边的图称为简单图；一个无环，一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图但允许有多重边的图称为多重图 以点以点v v为端点的边的个数称为为端点的边的个数称为v v的次，记为的次，记为dG(v)dG(v)或或d(v)d(v)次为奇数的点，称之为奇点；次为偶数的点，称。
次为奇数的点，称之为奇点；次为偶数的点，称之为偶点之为偶点 称次为称次为1 1的点为悬挂点，悬挂点的关连边称为悬挂的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点边，次为零的点称为孤立点9/21/20248 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念 证明：显然，在计算各点的次时，每条边被它证明：显然，在计算各点的次时，每条边被它的端点各用了一次的端点各用了一次 定理定理1 1 图图G=(VG=(V，，E)E)中，所有点的次之和是边数的两倍，中，所有点的次之和是边数的两倍，即：即：9/21/20249 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念定理定理2 2 任一个图中，奇点的个数为偶数任一个图中，奇点的个数为偶数 证明证明: :设设V V1 1和和V V2 2分别是分别是G G中奇点和偶点的集合，中奇点和偶点的集合，由定理由定理1 1，有：，有： 因因 是偶数，是偶数， 也是偶数，故也是偶数，故 必定也是偶必定也是偶数，从而数，从而V V1 1的点数是偶数。
的点数是偶数9/21/202410 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念 给定一个图给定一个图G=(V,E)G=(V,E)和一个点、边交错序列和一个点、边交错序列 , , 如果满足：如果满足： (t=1，2，…，k-1)则称为一条联结则称为一条联结 的链，记为的链，记为 称点称点 为链的中间点为链的中间点9/21/202411 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化图的相关概念图的相关概念 链链 中，若中，若 ，则称之为一个圈，记为，则称之为一个圈，记为 。
若链若链 中，点中，点 都是不同的，则称都是不同的，则称之为初等链；若圈之为初等链；若圈 中，中， 都是不同的，则称之为初等圈都是不同的，则称之为初等圈 若链若链( (圈圈) )中含的边均不相同，则称之为简单圈以中含的边均不相同，则称之为简单圈以后说到链后说到链( (圈圈) )，除非特别交代，均指初等链，除非特别交代，均指初等链( (圈圈) )9/21/202412 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化例子例子 是一条简单链，但不是初是一条简单链，但不是初等链，等链， 是一条初等链是一条初等链 是一个初等圈，是一个初等圈， 是是简单圈，但不是初等圈。
简单圈，但不是初等圈9/21/202413 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化连通图连通图 图图G G中，若任何两点之间至少有一条链，则称中，若任何两点之间至少有一条链，则称G G是连通图，否则称为不连通图是连通图，否则称为不连通图 若若G G是不连通图，它的每个连通的部分称为是不连通图，它的每个连通的部分称为G G的一的一个连通分图个连通分图( (也简称分图也简称分图) )思考：右图是连通图吗？思考：右图是连通图吗？9/21/202414 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化支撑子图支撑子图 给了一个图给了一个图G=(VG=(V，，E)E)，如果，如果G′=(V′G′=(V′，，E′)E′)，，使使V=V′V=V′及及E′∈E E′∈E ，则称，则称G′G′是是G G的一个支撑子图的一个支撑子图 设设v∈V(G)v∈V(G)，用，用G G−v v表示从图表示从图G G中去掉点中去掉点v v及及v v的关的关联边后得到的一个图。
联边后得到的一个图9/21/202415 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化和有向图有关的概念和术语和有向图有关的概念和术语 设给定一个有向图，设给定一个有向图，D=(VD=(V，，A)A)，从，从D D中去掉所有弧上的箭头，中去掉所有弧上的箭头，就得到一个无向图，称之为就得到一个无向图，称之为D D的基础图，记之为的基础图，记之为G(D)G(D) 给定给定D D中的一条弧中的一条弧a=(ua=(u，，v)v)，称，称u u为为a a的始点，的始点，v v为为a a的终点，的终点，称弧称弧a a是从是从u u指向指向v v的 设设 是是D D中的一个点弧交错序列，如果这个序列在中的一个点弧交错序列，如果这个序列在基础图基础图G(D)G(D)中所对应的点边序列是一条链，则称这个点弧交错中所对应的点边序列是一条链，则称这个点弧交错序列是序列是D D的一条链类似定义圈和初等链的一条链类似定义圈和初等链( (圈圈) )。
如果如果 是是D D中的一条链，并且对中的一条链，并且对t=1t=1，，2 2，，……，，k-1k-1，均有，均有 ，称之为从，称之为从 的一条路若路的第一个点和的一条路若路的第一个点和最后一点相同，则称之为回路类似定义初等路最后一点相同，则称之为回路类似定义初等路( (回路回路) )9/21/202416 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化例子例子 是一个回路；是一个回路； 是从是从v v1 1到到v v6 6的路；的路； 是一条链，但不是路。
是一条链，但不是路 注：对无注：对无向图，链与路向图，链与路( (圈与回圈与回路路) )两个概念是一致的两个概念是一致的9/21/202417 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树树 树：一类极其简单然而却很有用的图树：一类极其简单然而却很有用的图 树的定义：树的定义： 一个无圈的连通图称为树一个无圈的连通图称为树9/21/202418 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质定理定理3 3 设图设图G=(VG=(V，，E)E)是一个树，是一个树，p(G)≥2p(G)≥2，则，则G G中至少有两个悬中至少有两个悬挂点 证明证明: :令令 是是G G中含边数最多的一条初等链，因中含边数最多的一条初等链，因p(G)≥2p(G)≥2，并且，并且G G是连通的，故链是连通的，故链P P中至少有一条边，从而中至少有一条边，从而v v1 1与与v vk k是不同的。
是不同的 现在来证明：现在来证明：v v1 1是悬挂点，即是悬挂点，即d(vd(v1 1)=1)=1 用反证法，如果用反证法，如果d(vd(v1 1)≥2)≥2，则存在边，则存在边 且且m≠2m≠2若点v vm m不不在在P P上，那么上，那么 是是G G中的一条初等链，它含的边数比中的一条初等链，它含的边数比P P多多一条，这与一条，这与P P是含边数最多的初等链矛盾若点是含边数最多的初等链矛盾若点v vm m在在P P上，那么上，那么 是是G G中的一个圈，这与树的定义矛盾于是必有中的一个圈，这与树的定义矛盾于是必有d(vd(v1 1)=1)=1，即，即v v1 1是悬挂点同理可证是悬挂点同理可证v vk k也是悬挂点，因而也是悬挂点，因而G G至少有两个悬挂点至少有两个悬挂点9/21/202419 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质定理定理4 4 图图G=(VG=(V，，E)E)是一个树的充分必要条件是是一个树的充分必要条件是G G不含不含圈，且恰有圈，且恰有p p−1 1条边。
条边 证明：必要性设证明：必要性设G G是一个树，根据定义，是一个树，根据定义，G G不含不含圈，故只要证明圈，故只要证明G G恰有恰有p p −1 1条边对点数条边对点数p p施行数学归施行数学归纳法p=1p=1，，2 2时，结论显然成立假设对点数时，结论显然成立假设对点数p≤np≤n时，时，结论成立设树结论成立设树G G含含n+1n+1个点由定理个点由定理3 3，，G G含悬挂点，含悬挂点，设设v v1 1是是G G的一个悬挂点，考虑图的一个悬挂点，考虑图G G − v v1 1，易见，易见p(G p(G − v v1 1)=n)=n，，q(G q(G − v v1 1)=q(G) )=q(G) − 1 1因G G − v v1 1是是n n个点的树，个点的树，由归纳假设，由归纳假设，q(G q(G − v v1 1)=n )=n − 1 1，于是，于是q(G)=q(G q(G)=q(G − v v1 1)+1=(n)+1=(n−1)+1=n=p(G) 1)+1=n=p(G) −1 19/21/202420 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质定理定理4 4 图图G=(VG=(V，，E)E)是一个树的充分必要条件是是一个树的充分必要条件是G G不含不含圈，且恰有圈，且恰有p p−1 1条边。
条边 证明：充分性证明：充分性 只要证明只要证明G G是连通的用反证法，是连通的用反证法，设设G G是不连通的，是不连通的，G G含含s s个连通分图个连通分图G G1 1，，G G2 2，，……，，Gs(s≥2)Gs(s≥2)因每个G Gi i(i=1(i=1，，2 2，，……，，s)s)是连通的，并且是连通的，并且不含圈，故每个不含圈，故每个G Gi i是树设G Gi i有有p pi i个点，则由必要性，个点，则由必要性，G Gi i有有p pi i− 1 1条边，于是条边，于是 这与这与q(G)=p(G) q(G)=p(G) − 1 1的假设矛盾的假设矛盾9/21/202421 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质定理定理5 5 图图G G是树的充分必要条件是任意两个顶点之间是树的充分必要条件是任意两个顶点之间恰有一条链恰有一条链 证明证明 必要性 因因G G是连通的，故任两个点之间至是连通的，故任两个点之间至少有一条链但如果某两个点之间有两条链的话，那少有一条链。
但如果某两个点之间有两条链的话，那么图么图G G中含有圈，这与树的定义矛盾，从而任两个点之中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链间恰有一条链 充分性：设图充分性：设图G G中任两个点之间恰有一条链，那么中任两个点之间恰有一条链，那么易见易见G G是连通的如果是连通的如果G G中含有圈，那么这个圈上的两中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故个顶点之间有两条链，这与假设矛盾，故G G不含圈，于不含圈，于是是G G是树9/21/202422 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质由定理由定理5 5，很容易推出如下结论：，很容易推出如下结论： (1) (1) 从一个树中去掉任意一条边，则余下的图是从一个树中去掉任意一条边，则余下的图是不连通的由此可知，在点集合相同的所有图中，树不连通的由此可知，在点集合相同的所有图中，树是含边数最少的连通图是含边数最少的连通图 (2) (2) 在树中不相邻的两个点间添上一条边，则恰在树中不相邻的两个点间添上一条边，则恰好得到一个圈。
进一步地说，如果再从这个圈上任意好得到一个圈进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树去掉一条边，可以得到一个树9/21/202423 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质 定义定义 设图设图T=(VT=(V，，E′)E′)是图是图G=(VG=(V，，E)E)的支撑子图，的支撑子图，如果图如果图T=(VT=(V，，E′)E′)是一个树，则称是一个树，则称T T是是G G的一个支撑树的一个支撑树 若若T=(VT=(V，，E′)E′)是是G=(VG=(V，，E)E)的一个支撑树，则显然，树的一个支撑树，则显然，树T T中边中边的个数是的个数是p(G) p(G) − 1 1，，G G中不属于树中不属于树T T的边数是的边数是q(G) q(G) − p(G)+1 p(G)+19/21/202424 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化树的性质树的性质定理定理6 6 图图G G有支撑树的充分必要条件是图有支撑树的充分必要条件是图G G是连通的。
是连通的 证明：必要性是显然的证明：必要性是显然的 充分性设图充分性设图G G是连通图，如果是连通图，如果G G不含圈，那么不含圈，那么G G本身是一个本身是一个树，从而树，从而G G是它自身的一个支撑树现设是它自身的一个支撑树现设G G含圈，任取一个圈，含圈，任取一个圈，从圈中任意地去掉一条边，得到图从圈中任意地去掉一条边，得到图G G的一个支撑子图的一个支撑子图G G1 1如果G G1 1不含圈，那么不含圈，那么G G1 1是是G G的一个支撑树的一个支撑树( (因为易见因为易见G G1 1是连通的是连通的) )；如果；如果G G1 1仍含圈，那么从仍含圈，那么从G G1 1中任取一个圈，从圈中再任意去掉一条边，中任取一个圈，从圈中再任意去掉一条边，得到图得到图G G的一个支撑子图的一个支撑子图G G2 2，如此重复，最终可以得到，如此重复，最终可以得到G G的一个的一个支撑子图支撑子图G Gk k，它不含圈，于是，它不含圈，于是G Gk k是是G G的一个支撑树的一个支撑树思考：该定理的充分性证明有什么作用？思考：该定理的充分性证明有什么作用？9/21/202425 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化最小支撑树问题最小支撑树问题 这里所说的这里所说的““权权””，是指与边有关的数量指标。
根据实际，是指与边有关的数量指标根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等 赋权图被广泛应用于工程技术及科学生产管理等领域的最赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一优化问题最小支撑树问题就是赋权图上的最优化问题之一定义定义 给图给图G=(VG=(V，，E)E)，对，对G G中的每一条边中的每一条边 ，相应，相应地有一个数地有一个数w wijij，则称这样的图，则称这样的图G G为赋权图，为赋权图，w wijij称为称为边边 上的权9/21/202426 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化最小支撑树问题最小支撑树问题 设有一个连通图设有一个连通图G=(VG=(V，，E)E)，每一边，每一边e= e= ，有，有一个非负权：一个非负权：w(e)=ww(e)=wijij (w (wijij≥0)≥0) 定义定义 如果如果T=(VT=(V，，E′)E′)是是G G的一个支撑树，称的一个支撑树，称E′E′中所有边的权之和为支撑树中所有边的权之和为支撑树T T的权，记为的权，记为w(T)w(T)。
即：即： 如果支撑树如果支撑树T T* * 的权的权w(Tw(T* *) )是是G G的所有支撑树的权中的所有支撑树的权中最小者，则称最小者，则称T T* *是是G G的最小支撑树的最小支撑树( (简称最小树简称最小树) )即9/21/202427 湖州师范学院商学院湖州师范学院商学院 一、图与树一、图与树第八讲第八讲 图与网络优化图与网络优化最小支撑树问题最小支撑树问题 1. 1. 避圈法：从图中任取一点避圈法：从图中任取一点 令令 ，图中其余的点都在，图中其余的点都在 中；从中；从 与与 的连线中找出最小边，这条边一定在最小支撑树的连线中找出最小边，这条边一定在最小支撑树内，不停重复，一直到图中所有点均包含在内，不停重复，一直到图中所有点均包含在V V中为止 2. 2. 破圈法：任取一个圈，从圈中去掉一条权最大的边破圈法：任取一个圈，从圈中去掉一条权最大的边( (如如果有两条或两条以上的边都是权最大的边，则任意去掉其中一果有两条或两条以上的边都是权最大的边，则任意去掉其中一条条) )。
在余下的图中，重复这个步骤，直至得到一个不含圈的图在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树为止，这时的图便是最小树下面介绍两个求解最小支撑树的方法下面介绍两个求解最小支撑树的方法9/21/202428 湖州师范学院商学院湖州师范学院商学院 例：例： 如图如图S,A,B,C,D,E,T代表村镇代表村镇,村镇之间的连村镇之间的连线上赋予了权值线上赋予了权值(可代表距离可代表距离,费用费用,流量等流量等)现沿图中现沿图中连线架设电线连线架设电线,使各村镇全部通电使各村镇全部通电,问如何架设使电线问如何架设使电线总长最短总长最短.(该图称为赋权图或无向网络该图称为赋权图或无向网络).第八讲第八讲 图与网络优化图与网络优化9/21/202429 湖州师范学院商学院湖州师范学院商学院最小支撑树总长=2+2+1+3+1+5=14第八讲第八讲 图与网络优化图与网络优化9/21/202430 湖州师范学院商学院湖州师范学院商学院电线总长=2+2+1+3+1+5=149/21/202431 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化引例引例 已知如下图所示的单行线交通网，每弧旁的数已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。
现在某人要字表示通过这条单行线所需要的费用现在某人要从从v v1 1出发，通过这个交通网到出发，通过这个交通网到v v8 8去，求总费用最小去，求总费用最小的旅行路线的旅行路线9/21/202432 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化引例引例结论结论1 1：：由上例可见，从由上例可见，从v1v1到到v8v8的旅行路线有很多；的旅行路线有很多；结论结论2 2：：不同的路线所需总费用是不同的；不同的路线所需总费用是不同的；结论结论3 3：：用图的语言来描述，从用图的语言来描述，从v1v1到到v8v8的一条旅行路的一条旅行路线就是图中从线就是图中从v1v1到到v8v8的一条路；一条旅行路线的总的一条路；一条旅行路线的总费用就是相应的从费用就是相应的从v1v1到到v8v8的路中所有弧旁数字之和的路中所有弧旁数字之和9/21/202433 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化一般意义的最短路问题一般意义的最短路问题 给定一个赋权有向图，即给了一个有向图给定一个赋权有向图，即给了一个有向图D=(VD=(V，，A)A)，对每一个弧，对每一个弧a=(va=(vi i，，v vj j) )，相应地赋予了权数；又给定，相应地赋予了权数；又给定D D中的两个顶点中的两个顶点v vs s，，v vt t。
设设P P是是D D中从中从v vs s到到v vt t的一条路，定的一条路，定义路义路P P的权是的权是P P中所有弧的权之和，记为中所有弧的权之和，记为w(P)w(P)最短路问最短路问题就是要在所有从题就是要在所有从v vs s到到v vt t的路中，求一条权最小的路，的路中，求一条权最小的路，即求一条从即求一条从v vs s到到v vt t的路的路P P0 0，使：，使： 上上式中对式中对D D中所有从中所有从v vs s到到v vt t的路的路P P取最小，称取最小，称P P0 0是从是从v vs s到到v vt t的最短路路的最短路路P P0 0的权称为从的权称为从v vs s到到v vt t的距离，记为的距离，记为d d(v(vs s，，v vt t) )显然，d(vd(vs s，，v vt t) )与与d(vd(vt t，，v vs s) )不一定相等不一定相等9/21/202434 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化最短路算法最短路算法 DijkstraDijkstra算法的基本思想：从算法的基本思想：从v vs s出发，逐步向外探出发，逐步向外探寻最短路。
执行过程中，与每个点对应，记录下一个数寻最短路执行过程中，与每个点对应，记录下一个数( (称为这个点的标号称为这个点的标号) )，它或者表示从，它或者表示从v vs s到该点的最短路到该点的最短路的权的权( (称为称为P P标号标号) )，或者是从，或者是从v vs s到该点的最短路的权的到该点的最短路的权的上界上界( (称为称为T T标号标号) )，方法的每一步是去修改，方法的每一步是去修改T T标号，并且标号，并且把某一个具把某一个具T T标号的点改变为具标号的点改变为具P P标号的点，从而使标号的点，从而使D D中中具具P P标号的顶点数多一个，这样，至多经过标号的顶点数多一个，这样，至多经过p p−1 1步，就可步，就可以求出从以求出从v vs s到各点的最短路到各点的最短路9/21/202435 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化DijkstraDijkstra算法算法 P P，，T T分别表示某个点的分别表示某个点的P P标号、标号、T T标号，标号， 为了在求出从为了在求出从v vs s到各点的距离的同时，也求出从到各点的距离的同时，也求出从v vs s到各点的最短路，给每个点到各点的最短路，给每个点v v以一个以一个λλ值。
算法终止时，值算法终止时，如果如果λ(v)=vλ(v)=vm m，表示在从，表示在从v vs s到到v v的最短路上，的最短路上，v v的前一个的前一个点是点是v vm m；；λ(v)=0λ(v)=0表示表示v=vv=vs s9/21/202436 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化例题例题 用用DijkstraDijkstra方法求前例中从方法求前例中从v v1 1到各个顶点的最短路？到各个顶点的最短路？标标P(vP(v1 1)=0)=0其余点标其余点标T(vT(vi i)= +∞)= +∞，，i i＝＝2 2，，3 3，，……，，9 9；；T(vT(v2 2) )＝＝minmin｛｛ +∞ +∞ ，，0 0＋＋6 6｝＝｝＝6 6，，λ(vλ(v2 2)=v)=v1 1；；T(vT(v3 3) )＝＝minmin｛｛ +∞ +∞ ，，0 0＋＋3 3｝＝｝＝3 3，，λ(vλ(v3 3)=v)=v1 1；；T(vT(v4 4) )＝＝minmin｛｛ +∞ +∞ ，，0 0＋＋1 1｝＝｝＝1 1，，λ(vλ(v4 4)=v)=v1 1；；将具有最小将具有最小T T标号的标号的v v4 4点的标号改为点的标号改为P P标号：标号：P(vP(v4 4) )＝＝1 1；；T(vT(v6 6) )＝＝minmin｛｛ +∞ +∞ ，，1 1＋＋1010｝＝｝＝1111，，λ(vλ(v6 6)=v)=v4 4；； 将具有最小将具有最小T T标号的标号的v v3 3点的标号改为点的标号改为P P标号：标号：P(vP(v3 3) )＝＝3 3；；T(vT(v2 2) )＝＝minmin｛｛ 6 6 ，，3 3＋＋2 2｝＝｝＝5 5，，λ(vλ(v2 2)=v)=v3 3；；将具有最小将具有最小T T标号的标号的v v2 2点的标号改为点的标号改为P P标号：标号：P(vP(v2 2) )＝＝5 5；；9/21/202437 湖州师范学院商学院湖州师范学院商学院例题例题 用用DijkstraDijkstra方法求前例中从方法求前例中从v v1 1到各个顶点的最短路？到各个顶点的最短路？T(vT(v5 5) )＝＝minmin｛｛ +∞ +∞ ，，5 5＋＋1 1｝＝｝＝6 6，，λ(vλ(v5 5)=v)=v2 2；； 将具有最小将具有最小T T标号的标号的v v5 5点的标号改为点的标号改为P P标号：标号：P(vP(v5 5) )＝＝6 6；； T(vT(v6 6) )＝＝minmin｛｛ 11 11 ，，6 6＋＋4 4｝＝｝＝1010，，λ(vλ(v6 6)=v)=v5 5；； T(vT(v7 7) )＝＝minmin｛｛ +∞ +∞ ，，6 6＋＋3 3｝＝｝＝9 9，，λ(vλ(v7 7)=v)=v5 5；； T(vT(v8 8) )＝＝minmin｛｛ +∞ +∞ ，，6 6＋＋6 6｝＝｝＝1212，，λ(vλ(v8 8)=v)=v5 5；； 将具有最小将具有最小T T标号的标号的v v7 7点的标号改为点的标号改为P P标号：标号：P(vP(v7 7) )＝＝9 9；； T(vT(v8 8) )＝＝minmin｛｛ 12 12 ，，9 9＋＋4 4｝＝｝＝1212，，λ(vλ(v8 8)=v)=v5 5；； 将具有最小将具有最小T T标号标号v v6 6点的标号改为点的标号改为P P标号：标号：P(vP(v6 6) )＝＝1111；；将具有最小将具有最小T T标号标号v v8 8点的标号改为点的标号改为P P标号：标号：P(vP(v8 8) )＝＝1212；；9/21/202438 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化DijkstraDijkstra算法缺陷算法缺陷 DijkstraDijkstra算法只适用于所有算法只适用于所有w wijij≥0≥0的情形，当赋权的情形，当赋权有向图中存在负权时，则算法失效。
例如在下图所示有向图中存在负权时，则算法失效例如在下图所示的赋权有向图中，如果用的赋权有向图中，如果用DijkstraDijkstra方法，可得出从方法，可得出从v v1 1到到v v2 2的最短路的权是的最短路的权是1 1，但这显然是不对的，因为从，但这显然是不对的，因为从v v1 1到到v v2 2的最短路是的最短路是(v(v1 1，，v v3 3，，v v2 2) )，权是，权是-1-19/21/202439 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化练习题练习题V1V2V3V4V5V6V798528737143109/21/202440 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化 Dijkstra Dijkstra算法另一种写法算法另一种写法初始值第一次 第二次第三次第四次T（）{0} ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞P（）+wijT（）P（）+wijT（）P（）+wijT（）P（）+wijT（）0+6 0+ 30+ 10+ ∞0+ ∞0+ ∞0+ ∞0+ ∞{1}36∞∞∞∞∞1+101+∞ 1+∞1+∞1+∞1+∞1+∞6{3}∞11∞∞∞3+23+∞3+∞3+∞3+∞3+∞{5}∞11∞∞∞5+15+∞5+∞5+∞5+∞{6}11∞∞∞9/21/202441 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化 Dijkstra Dijkstra算法另一种写法算法另一种写法初始值第五次 第六次第七次第八次T（） 11 ∞ ∞ ∞P（）+wijT（）P（）+wijT（）P（）+wijT（）P（）+wijT（）{6}6+46+36+66+∞10{9}∞129+49+ ∞9+ ∞{10}10+ ∞10+ ∞{12}∞9/21/202442 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化迭代算法迭代算法 迭代算法是迭代算法是当赋权有向图中存在具负权弧时，求当赋权有向图中存在具负权弧时，求最短路的方法。
最短路的方法 为方便起见，不妨设从任一点为方便起见，不妨设从任一点vivi到任一个点到任一个点v vj j都有一条弧都有一条弧( (如果在如果在D D中，中， ，则添，则添加弧加弧(v(vi i，，v vj j) )令w wijij=+∞)=+∞) 显然，从显然，从v vs s到到v vj j的最短路总是从的最短路总是从v vs s出发，沿着一条出发，沿着一条路到某个点路到某个点v vi i，再沿，再沿(v(vi i，，v vj j) )到到v vj j的的( (这里这里v vi i可以是可以是v vs s本本身身) )，明显可知，从，明显可知，从v vs s到到v vi i的这条路必定是从的这条路必定是从v vs s到到v vi i的的最短路，所以最短路，所以d(vd(vs s，，v vj j) )必满足如下方程：必满足如下方程： 9/21/202443 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化迭代算法迭代算法 为了求得这个方程的解为了求得这个方程的解d(vd(vs s，，v v1 1) )，，d(vd(vs s，，v v2 2) )，，……，，d(vd(vs s，，v vp p) )，可用如下递推公式：，可用如下递推公式：开始时，令：开始时，令： ,(j=1 ,(j=1，，2 2，，……，，p)p)对对t=2,…3, t=2,…3, ，，j=1j=1，，2 2，，……，，p p若进行到某一步，例如第若进行到某一步，例如第k k步时，对所有步时，对所有j=1j=1，，2 2，，……，，p p，有：，有：则则 ，即为，即为vsvs到各点的最短路的权。
到各点的最短路的权9/21/202444 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题第八讲第八讲 图与网络优化图与网络优化迭代算法迭代算法例题例题 求右图所示赋求右图所示赋权有向图中从权有向图中从v v1 1到各点的到各点的最短路9/21/202445 湖州师范学院商学院湖州师范学院商学院 二、最短路问题二、最短路问题 第八讲第八讲 图与网络优化图与网络优化迭代算法迭代算法例题例题 到从V1V2V3V4V5V6V7V8t=1t=2t=3t=4V10-1-23V2602V3-30-51V4802V5-10V61017V7-10V8-3-500-1-230-5-2-71-150-5-2-7-3-1-50-5-2-7-3-1-5669/21/202446 湖州师范学院商学院湖州师范学院商学院 第八讲第八讲 图与网络优化图与网络优化 三、最大流问题三、最大流问题 流流(Flow)(Flow)就是将目标由一个地点运送就是将目标由一个地点运送到另一个地点到另一个地点. .如如: :公路中的交通流公路中的交通流, ,控制系统中的控制系统中的信息流信息流, ,供水系统中的水流供水系统中的水流, ,金融系统中的现金流金融系统中的现金流, ,邮政系统中的信件流邮政系统中的信件流, ,等等等等. .它们的共同问题是它们的共同问题是, ,希希望经过输送系统望经过输送系统, ,将目标从一个地点运送到另一个将目标从一个地点运送到另一个地点的运输量最大地点的运输量最大, ,或者将一定数量的目标在该系或者将一定数量的目标在该系统中从一个地点输送到另一个地点的费用最小统中从一个地点输送到另一个地点的费用最小. .这这就是网络中的最大流问题和最小费用最大流问题就是网络中的最大流问题和最小费用最大流问题. .9/21/202447 湖州师范学院商学院湖州师范学院商学院 容量网络容量网络是指对网络上的每一条弧是指对网络上的每一条弧, ,都给出都给出一个最大的通过能力一个最大的通过能力, ,称为该弧的容量称为该弧的容量, ,记为记为或简记为或简记为 , ,这样的网络称为容量网络这样的网络称为容量网络. . 在容量网络中规定一个发点在容量网络中规定一个发点( (源点源点)s)s和一个收点和一个收点( (汇点汇点)t,)t,其余的点称为中间点其余的点称为中间点. . 网络的最大流网络的最大流是指是指: :网络中从发点网络中从发点到收点之间允许通过的最大流量到收点之间允许通过的最大流量. . 第八讲第八讲 图与网络优化图与网络优化 1、最大流问题相关概念、最大流问题相关概念9/21/202448 湖州师范学院商学院湖州师范学院商学院 第八讲第八讲 图与网络优化图与网络优化 我们只研究一个发点和一个收点的情我们只研究一个发点和一个收点的情况况. .对于多个发点和多个收点的情况可将若干对于多个发点和多个收点的情况可将若干个发点合并为一个新的发点对于收点也如此处个发点合并为一个新的发点对于收点也如此处理理. .9/21/202449 湖州师范学院商学院湖州师范学院商学院流流（（flowflow））是指加在网络上的一组负载是指加在网络上的一组负载. .对加对加在弧在弧 上的流上的流, ,记为记为 或或简记为简记为 , ,当当 时称为零流时称为零流. .可行流可行流（（feasible flowfeasible flow）：）：在容量网络上满足下列三在容量网络上满足下列三个条件的一组流称为可行流：个条件的一组流称为可行流：(1)(1)容量限制条件容量限制条件: :对所有的弧有对所有的弧有(2) (2) 中间点平衡条件中间点平衡条件: :(3) (3) 若以若以v(fv(f) )表示网络中从表示网络中从s s到到t t的净输出量的净输出量, ,则有则有 流和可行流流和可行流:9/21/202450 湖州师范学院商学院湖州师范学院商学院 第八讲第八讲 图与网络优化图与网络优化 任何容量网络上一定存在可行流任何容量网络上一定存在可行流, ,因因为零流就是可行流为零流就是可行流. . 所谓求网络最大流所谓求网络最大流, ,就是指在满足容就是指在满足容量限制条件和中间点平衡条件下量限制条件和中间点平衡条件下, ,使使v(f)v(f)值达值达到最大到最大. .9/21/202451 湖州师范学院商学院湖州师范学院商学院 增广链增广链: :如果在网络的发点和收点之如果在网络的发点和收点之间能找出一条链间能找出一条链, ,在这条链上所有的指向为在这条链上所有的指向为s→ts→t的弧的弧( (称为前向弧称为前向弧, ,记为记为 ), ),存在存在f
的最小截集的容量 第八讲第八讲 图与网络优化图与网络优化9/21/202456 湖州师范学院商学院湖州师范学院商学院求网络最大流的标号法求网络最大流的标号法 该算法是由该算法是由FordFord和和FulkersonFulkerson于于19561956年提出年提出, ,故称故称Ford-FulkersonFord-Fulkerson标号法算法的实质是：判断标号法算法的实质是：判断网络中是否存在增广链网络中是否存在增广链, ,并将其找出来并将其找出来. .算法步骤算法步骤: : 1 1、首先给发点、首先给发点s s标号标号, ,记为记为 , ,括号中第一个数字是使这个点得到标号的前一括号中第一个数字是使这个点得到标号的前一个点的代号个点的代号, ,第二个数字表示从上一个标号点到第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值这一标号点的流量的最大允许调整值; ; 第八讲第八讲 图与网络优化图与网络优化9/21/202457 湖州师范学院商学院湖州师范学院商学院2 2 2 2、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点. . . . ⑴ ⑴ ⑴ ⑴ 考虑从标号点考虑从标号点考虑从标号点考虑从标号点i i i i出发的弧出发的弧出发的弧出发的弧(i,j),(i,j),(i,j),(i,j),如有如有如有如有 则不给则不给则不给则不给j j j j点标号点标号点标号点标号; ; ; ;若有若有若有若有 则对则对则对则对j j j j点标号点标号点标号点标号, , , ,记为记为记为记为 其中其中其中其中i i i i表示表示表示表示j j j j点的标号是从点的标号是从点的标号是从点的标号是从i i i i点延伸过来的点延伸过来的点延伸过来的点延伸过来的, , , ,⑵ ⑵ ⑵ ⑵ 考虑所有指向考虑所有指向考虑所有指向考虑所有指向i i i i的弧的弧的弧的弧(j,i),(j,i),(j,i),(j,i),如有如有如有如有 对对对对j j j j点不标号点不标号点不标号点不标号, , , ,若若若若有有有有 则对则对则对则对j j j j点标号点标号点标号点标号, , , ,记为记为记为记为求网络最大流的标号法求网络最大流的标号法—Ford-Fulkerson—Ford-Fulkerson标号标号法法 第八讲第八讲 图与网络优化图与网络优化2 2 2 2、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点、找出与已标号点相邻的所有未标号点. . . . 求网络最大流的标号法求网络最大流的标号法—Ford-Fulkerson—Ford-Fulkerson标号标号法法9/21/202458 湖州师范学院商学院湖州师范学院商学院⑴ ⑴ 标号过程中断标号过程中断,t,t点得不到标号点得不到标号, ,说明网络中说明网络中不存在增广链不存在增广链, ,网络中给定的流就是最大流网络中给定的流就是最大流. .计计算结束算结束; ;⑵ t⑵ t点得到标号点得到标号, ,这时反向追踪这时反向追踪, ,在网络中找到在网络中找到一条从一条从s s到到t t 的由标号点和相应的弧连结而成的由标号点和相应的弧连结而成的增广链的增广链. .3 3、重复步骤、重复步骤2,2,可能出现两种结局可能出现两种结局: :求网络最大流的标号法求网络最大流的标号法—Ford-Fulkerson—Ford-Fulkerson标号标号法法 第八讲第八讲 图与网络优化图与网络优化9/21/202459 湖州师范学院商学院湖州师范学院商学院5 5 5 5、抹去网络图中的所有标号、抹去网络图中的所有标号、抹去网络图中的所有标号、抹去网络图中的所有标号, , , ,重复第重复第重复第重复第1 1 1 1到第到第到第到第4 4 4 4步步步步, , , ,一一一一直到在网络中找不到任何增广链直到在网络中找不到任何增广链直到在网络中找不到任何增广链直到在网络中找不到任何增广链, , , ,即出现第即出现第即出现第即出现第3 3 3 3步的结步的结步的结步的结局局局局(1)(1)(1)(1)为止为止为止为止, , , ,这时网络中的流量为网络的最大流这时网络中的流量为网络的最大流这时网络中的流量为网络的最大流这时网络中的流量为网络的最大流. . . .4 4 4 4、修改流量、修改流量、修改流量、修改流量: : : :设在网络中原有的流量为设在网络中原有的流量为设在网络中原有的流量为设在网络中原有的流量为f f f f，并且以，并且以，并且以，并且以为调整量，则：为调整量，则：为调整量，则：为调整量，则： 第八讲第八讲 图与网络优化图与网络优化求网络最大流的标号法求网络最大流的标号法—Ford-Fulkerson—Ford-Fulkerson标号标号法法9/21/202460 湖州师范学院商学院湖州师范学院商学院 例题：用标号法求下面网络从例题：用标号法求下面网络从s s到到t t的最大流量的最大流量, ,并找出该网络的最小截集的容并找出该网络的最小截集的容量量. . 第八讲第八讲 图与网络优化图与网络优化9/21/202461 湖州师范学院商学院湖州师范学院商学院 因为因为t t点得到标号点得到标号, ,用反向追踪法可找出用反向追踪法可找出从从s s到到t t的一条增广链的一条增广链, ,用红线标出用红线标出; ; 修改增广链上的流量修改增广链上的流量修改增广链上的流量修改增广链上的流量: : : : 其余弧上的流量不变其余弧上的流量不变其余弧上的流量不变其余弧上的流量不变, , , ,于是得到网络上的一个新于是得到网络上的一个新于是得到网络上的一个新于是得到网络上的一个新可行流可行流可行流可行流, , , ,重复上述的标号过程重复上述的标号过程重复上述的标号过程重复上述的标号过程, , , ,转下一步转下一步转下一步转下一步; ; ; ; 第八讲第八讲 图与网络优化图与网络优化9/21/202462 湖州师范学院商学院湖州师范学院商学院 标号中断标号中断,t,t点得不到标号点得不到标号, ,网络中没网络中没有增广链有增广链, ,该网络的可行流就是最大流该网络的可行流就是最大流, ,最大最大流量为流量为 第八讲第八讲 图与网络优化图与网络优化9/21/202463 湖州师范学院商学院湖州师范学院商学院下面求该网络的最小截集下面求该网络的最小截集: : 第八讲第八讲 图与网络优化图与网络优化9/21/202464 湖州师范学院商学院湖州师范学院商学院9/21/202465 。
