1、2022-6-71第八章第八章第一节 图与网络的基本知识第二节 树第三节 最短路问题第四节 最大流问题第五节 最小费用流问题讲五节：2022-6-728-1 8-1 图与网络的基本知识图与网络的基本知识一、图与网络的基本概念一、图与网络的基本概念1、图及其分类是反映对象之间关系的一种工具。例如，在一个人群中，对相互认识这种关系可以用图来表示。赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)陈(v7)若将“相互认识”的关系改成“认识”，可以用带箭头的连线表示。顶点边 一个图是由点集V=vi和V中元素的无序对的一个集合E=ek所构成的二元组,记为G=(V,E),V中的元素vi叫做,E中
2、的元素ek叫做。当V，E为有限集合时,G称为有限图,否则,称为无限图e1e2e3e4e5V=vi=v1,v2,v7E=ei=e1,e2,e5返回第八章目录返回第八章目录返回第八章目录2022-6-73例1 在图8-7中：V=v1,v2,v3,v4,v5 E=e1,e2,e3,e4,e5,e6两条边ei, ej 属于E，如果它们有公共端点u，则称ei,ej相邻。边ei,ej称为u的关联边。对于任一条边(vi,vj)属于E，如果边(vi,vj)端点无序，则它是无向边，此时图为无向图.图8-7是无向图.如果边(vi,vj)端点有序,即它表示以vi为始点,vj为终点的有向边(或称弧),这时图G称为有向
3、图。一条边的两个端点如果相同,称此边为环(自回路).如图8-7中的e1。两个点之间多于一条边的，称为多重边,如图8-7中的e4,e5 。其中：e1=(v1,v1) ；e2=(v1,v2) ；e3=(v1,v3)e4=(v2,v3) ；e5=(v2,v3) ；e6=(v3,v4)两个点u,v属于V,如果边(u,v)属于E,则称u,v两点相邻。u,v称为边(u,v)的端点。e1v1e2v2e4e5v3v4e6v5图 8-7e32022-6-74定义定义 2 2 不含环和多重边的图称为简单图简单图，含有多重边的图称为多重图多重图。定义义3 3 每一对顶点间都有边相连的无向简单图称为。有n个顶点的无向
4、完全图记作Kn 。每一对顶点间有且仅有一条有向边的简单图，称为。(b)(c)(a)(d)图 8-8简单图简单图多重图多重图2022-6-75定义定义4 4 图G( V,E ) 的点集V可以分为两个非空子集X，Y，即XUYV,XYf，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G( X,Y,E )。例如图8-9中的(a)是明显的二部图，点集X：v1,v3,v5)，Y：v2,v4,v6，(b)也是二部图，但是不像 (a)那样明显，改画为(c)时可以清楚地看出。v1v2v6v5v3v4(a)v4v1v3v2(b)v1v2v4v3(c) 图 8-920
5、22-6-762. 顶点的次定义定义5 以点v为端点的边数叫做点v的,记作deg(v),简记d(v)。如图8-7中点v1的次d(v1)=4,因为边e1要计算两次。点v3的次d(v3)=4，点v4的次d(v4)=1。次为1的点称为,连接悬挂点的边称为.如8-7图中v4,e6。次为零的点称为，如图8-7中的点v5。次为奇数的点称为。次为偶数的点称为。e1v1e2v2e4e5v3v4e6v5图 8-7e3 任何图中，顶点次数的总和等于边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。悬挂点悬挂边孤立点奇点偶点偶点2022-6-77定
6、理定理2 2 任何图中，次为奇数的顶点必为偶数个。证明：设V1和V2分别为G中奇点与偶点的集合(V1UV2=V).由定理1知122)()()(VvVvVvmvvdvd是偶数。必为偶数，即所以是偶数，是若干个偶数之和，也为偶数，而由于112)()(2VvdvdmVvVv定义定义6 6 有向图中,以vi为始点的边数称为点vi的，用d+(vi)表示；以vi为终点的边数称为点vi的，用d(vi)表示。点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等于出次之和。3. 3. 子图子图 定义定义7 7 图G =(V,E),若E是E的子集,V是V的子集，且E中的边仅与V中的顶点相关联，则
7、称G =(V,E)是G的一个。特别地，若V=V，则G称为G的。2022-6-78v4v1v5v3v2v6v7e8e4e9e6e7(c)上图中，(b)为(a)的，(c)为(a) 的。4. 4. 在实际问题中，只用图来描述所研究对象之间的关系往往是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“”，权可以代表如距离、费用、通过能力（容量）等等。这种 (赋权图)。VV,EEVV,EE.且V=Vv5v6v3v2v1e1e6v5v4(b)v7v5v2v1e10e7e9e8v3e4e5e1e2e6v4v6(a)e32022-6-79二、连通图二、连通图e7v5v4v3v2v1v
8、6e1e3e4e5e6e8e9e10e2图 8-12()()()()。的一条链，链长为与接则称这个点边系列为连且的形式，成列可以排中某些点与边的交替系若无向图定义kvvktvveevevevGEVGttttkkiiiiiiiiiii0112110, 2 , 1,8定义定义9 无向图G中,连结vi0与vik的一条链，当vi0与vik是同一个点时,称此链为.圈中只有重复点而无重复边者为，既无重复点也无重复边者为，有向图当链(圈)上的边方向相同时,称为(回路 )。v1,e7,v5, e8,v1,e9,v4,e10,v2,e2,v1为一个圈。2022-6-710对于有向图可以类似于无向图定义链和圈，初
9、等链、圈，简单链、圈，此时不考虑边的方向。而当链（圈）上的边方向相同时，称为道路（回路）。e7v5v4v3v1v6v2e10e 11e3e2e5e9e8e1e6图 8-13e42022-6-711三、图的矩阵表示三、图的矩阵表示定义定义1111 网络(赋权)图G=(V,E),其边(vi ,vj)有权wij，构造矩阵A=(ai j)nn，其中其它0),(Evvwajiijij例例2 图示 8-14所示的图 其权矩阵为：0650760844580320430974290A称矩阵A为网络G的权矩阵。6v5v4v3v2v1754238图 8-1494v1v1v2v3v4v5v2v4v52022-6-7
10、12定义定义1212 对于图G=(V,E),|V|=n,构造一个矩阵A=(aij)nn,其中：其它0),(1Evvajiij则称矩阵A为图G的邻接矩阵。邻接矩阵。例例3 3 对图8-15所表示的图可以构造邻接矩阵A如下：v1v2v3v4v6v5 图图 8-15010000101010100010010010000100000110654321vvvvvvAv1v2v3v4v5v6G2022-6-713四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题1 .欧拉回路与道路定义定义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为。若存在一条回路，经过每边一次且仅一次，则称这条
11、回路为。具有欧拉回路的图称为（E图）。 无向连通图G是欧拉图，当且仅当G中无奇点。推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。 连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。连通有向图G有欧拉道路，当且仅当这个图中除去两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个顶点 的入次比出次少1。2022-6-7142. 2. 中国邮路问题中国邮路问题一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走
12、的总路程最短？国际上通称这个问题为中国邮路问题。用图论的语言描述：给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。中国邮路问题也可以转为如下问题中国邮路问题也可以转为如下问题：在连通图G=(V,E)中，求一个边集E1E，把G中属于E1的边均变为二重边得到图G*=G+E1，使其满足 G*无奇点,且L(E1)=Sl(e) (eE1)最小。 己知图G*=G+E1无奇点 ,则L(E1)=Sl(e) (eE1)最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。定理给出了中国邮路问题的一种算法，称为“奇偶点图上作
13、业法”，下面举例说明这个算法。2022-6-715例例 4 4 求解图 8-16所示网络的中国邮路问题v3v1v2v6v9v8v7v4v5图图 8-17v3v1v2v6v9v8v7v4v524344955644图图 8-1632022-6-716第二步第二步：调整可行方案，使重复边最多为一次。去掉(v2,v3),(v3v6),(v4,v7),(v7,v8)各两条，得到图 8-18 。重复边总长度下降为：l 12 + l 14 + l 69 +l 98=21v3v1v2v6v9v8v7v4v52434495546图图 8-19第三步第三步：检查图中每个初等圈是否满足定理条件(2)。如不满足则进行
14、调整，直至满足为止。检查图 8-18，发现圈v1v2v5 v4v1 总长度为24，而重复边的长为14，大于该圈总长度的一半，可以作一次调整，以(v2,v5),(v5,v4)代替(v1,v2),(v1,v4)，得到图 8-19，重复边总长度下降为： l 25 +l 45 + l 69 + l 98 =17v3v1v2v6v9v8v7v4v544335599图图 8-18462022-6-717再检查图 8-19，圈v2v3v6v9v8v5v2总长度为24，而重复边长为13。再次调整得图 8-20，重复边总长度为15。检查图 8-20,条件(1),(2)均满足 ，得到最优方案。图中任一欧拉回路即为
15、最优邮递路线。v3v1v2v6v9v8v7v4v52434495544图 8-20v3v1v2v6v9v8v7v4v544335599图图 8-1864v3v1v2v6v9v8v7v4v52434495546图图 8-1942022-6-7188-2树树一、树的概念和性质一、树的概念和性质例例5 5 乒乓球单打比赛抽签后,可用图来表示相遇情况,如图8-21所示。ECGKABD FHI JLMN运运 动动 员员图图 8-21销销 售售 科科检检 验验 科科新产品新产品 开发开发 科科技技 术术 科科生生 产产 科科设设 备备 科科供供 应应 科科动动 力力 科科人人 事事 科科总总 工工 程程
16、师师 财财 务务 科科生生 产产 副副 厂厂长长 经经 营营 副副 厂厂长长 图图 8-22厂长厂长定义定义1414 不含圈的无向连通图称为。树中次为1的点称为，次大于1的点称为例例6 6 某企业的组织结构可用图8-22表示树叶分枝点树返回第八章目录返回第八章目录返回第八章目录2022-6-719定理6 图T=(V,E),| V |=n,| E |= m,则下列关于树的说法是等价的：（1）T 是一棵树。（2）T 无圈，且m=n-1.（3）T 连通，且m=n-1。（4）T 无圈，但每加一新边即得唯一一个圈。（5）T 连通，但每舍去一边就不连通。（6）T 中任意两点，有唯一链相连。定义定义15 若
17、图G的生成子图是一棵树，则称该树为G的（支撑树）。或简称为图G的树。图G中属于生成树的边称为,不在生成树中的边称为。图8-23中(b)为(a)图的生成树,边e1,e2,e3,e7,e8,e9为树枝 ，e4,e5,e6,为弦。e3e4e1e2e6e1e2e7e8e9e5 (a)e3e7e8e9 (b) 图 8-23树枝弦2022-6-720定理定理7 7 图G=(V,E)有生成树的充分必要条件为G是连通图。求生成树的方法：1. 避圈法（加边法）在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止。（1）深探法（标号法）。步骤如下： 在点集V中任取一点v,给v以标号0。 若某
18、点u已得标号i，检查一端点为u的各边，另一端点是否均已标号。若有(u,w)边之w未标号,则给以标号i+1,记下边(u,w).令w代u,重复.若这样的边的另一端点均已有标号，就退到标号为i-1的点r以r代u，重复.直到全部得到标号为止。图 8-24 的(a)为标号过程，粗线边即为生成树,图8-24(b)即是生成树，也显示了标号过程。2022-6-721图 8-24740261012813591113(b)012345698101112137(a)(2) 广探法步骤如下：在点集V中任取一点v,给v以标号0。令所有标号为i的点集为Vi，检查Vi，V Vi中的边端点是否均已标号。对所有未标号之点均标以
19、i+1，记下这些边。 对标号为i+1的点重复步骤 。直到全部点得到标号为止。图 8-25(a)中 粗 线 边 就是 用 广 探 法生 成 的 树 ，也 可 表 示 为图8-25(b)图8-254211112222333(b)02343201122211(a)32022-6-722例例7 7 一个乡有9个自然村，其间道路如图 8-26(a)所示，要以v0村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？2. 破圈法在图G中任意取一个圈,从圈上任意舍弃一条边，将这个圈破掉,重复这个步骤直到图G中没有圈为止。v6v1v2v3v4v5v7v8v0(b)(a)v6v1v2v3v4v5v7v8v
20、0图 8-26解：解：用破圈法，任取一圈(v1,v2,v2,v1)，从中去掉边(v1,v2)，再选圈(v1,v8,v0,v1)去掉边(v1,v8)，依同样方法进行，直到无圈。图8-26( b)就是一种方案。2022-6-723321三、最小生成树问题三、最小生成树问题定义定义1616 连通图G=(V,E)，每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个生成树的权。，简称最小树。最小树的两种算法算法1 ：(Kruskal算法) 此法类似于求生成树的“避圈法”，步骤如下：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。v4v5(a
21、)v6v1v2v3v7v8v0111122334444555211v6v1v2v3v4v5v7v8v0(b)122图 8-272022-6-724定理定理8 8 用 Kruskal 算法得到的子图T*=(e1,e2,en-1)是一棵最小树。然后按照边的排列顺序，取定：(v0,v2)=1，(v2,v3)=1，(v3,v4)=1，(v1,v8)=1，(v0,v1)=2 ，(v0,v6)=2，(v5,v6)=2。由于下一个未选取边中的最小权边(v0,v3)与已选边e1,e2构成圈，所以排除。选e8=(v6,v7)。得到(b)就是图G的一棵最小树,它的权是13。 图G的生成树T为最小树，当且仅当对任一
22、弦e来说，e是T+e中与之对应的圈 me中的最大权边。 若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为。 有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。根树中入次为0的点称为。根树中出次为0的点称为，其它顶点称为。由根到某一顶点vi的道路长度（设每边长度为1），称为vi点的。2022-6-725定义定义1919 在根树中,若每个顶点的出次小于或等于m,称这棵树为m叉树,若每个顶点的出次恰好等于m或零,则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。图8-29 所示的树是根树，其中v1为根，v1,v2,v3,v4,v8为分枝点，其余各点为叶
23、，顶点v2,v3,v4的层次为1,顶点v11的层次为3等等。图 8-29 v11v1v2v3v4v5v6v7v8v9v10(a)(b)图 8-30例如图8-30中(a)为完全三叉树、(b)为四叉树。实际问题中常讨论叶子上带权的二叉树,令有s个叶子的二叉树T各叶子的权分别为pi,根到各叶子的距离(层次)为li(i=1,s),这样二叉树的总权数：siiilpTm1)(2022-6-7264 12 2 333满足总权最小的二叉树称为最优二叉树最优二叉树( (霍夫曼树）。霍夫曼树）。算法步骤为：将s个叶子按权由小至大排序 ,不失一般性，设p1p2ps。将二个具有最小权的叶子合并成一个分枝点，其权为p1
24、+p2,将新的分枝点作为一个叶子。令ss-1，若s=1停止，否则转(1)。例 9 s=6其权分别为4,3,3,2,2,1,求最优二叉要树。解：解：该树构造过程见图8-31。总权为14+2 4+2 3+3 2+3 2+4 2=38 图 8-31 1 223334569 1 2233345 6915421 233356此算法得到的树为最优二叉树，直观意义：叶子的距离是依权的递减而增加，所以总权最小。2022-6-727例10 最优检索问题使用计算机进行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册,E类15万册。问如何安排分检过程，可使总的运算(比
25、较)次数最小？解解:构造一棵具有5个叶子的最优二叉树,其叶子的权分别为50,20,5,10,15,见图8-32(a)所示,按(b)进行分类.总权为：m(T)=5 4+10 4+15 3+20 2+50 1=195图 8-32105151002050501530EABCD(a) Y NE?B?A?D?ABCDE N Y Y N N Y(b)分检过程是先把A类50万册从总数中分检出来,其次将B类20万册分检出来,然后再将E类15万册分检出来,最后再将D,C分检。2022-6-728例例1111 某厂购进一批原件，欲进行检验后按质量分为六等。已知一等品的概率为0.45，二等品的概率为0.25，三等品
26、0.12，四等品0.08，五等品0.05，等外品0.05。假设分等测试一次只能分辨出一种等级，而每次测试的时间皆为t。问如何安排测试过程，使期望的时间达到最短？解：解：构造 一棵具有6个叶子的最优二叉树，其叶子的权数为各等级品的概率，见图8-33所示。0.050.080.050.120.250.450.100.180.300.551.01 等品等外品5 等品4 等品 3 等品 2 等品测试顺序图 8-33期望最短测试时间就是最优二叉树的总权，经计算得：m(T)= (5 0.05+50.05+4 0.08+3 0.12+2 0.25 +10.45)t=2.13t2022-6-7298-3 8-3
27、 最短路问题最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权lij(lij=表示vi,vj间无边)，vs,vt为图中任意两点，求一条道路 m，使它是从vs到vt的所有路中总权最小的路。即最小mm),()(jivvijlL有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。一、一、Dijkstra 算法算法 基本步骤，采用标号法。可用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号，给vi点一个P标号时，表示从vs到vi点的最短路权，vi点的标号不再改变。给vi点一个T标号时，表示从vs到vi点的估计最短路权的上界，是一种临时标号
28、，凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n-1步就可以得到从始点到终点的最短路。返回第八章目录返回第八章目录返回第八章目录2022-6-730Dijkstra 算法步骤： (1)给vs以P标号，P(vs)=0，其余各点均给T标号T(vi)=+。 (2)若vi点为刚得到标号的点，考虑这样的点vj：(vi,vj)属于E，且vj为T标号。对vj的标号进行如下的更改：T(vj)=minT(vj),P(vi)+lij (3)比较所有具有T标号的点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P
29、标号。若全部点均为P标号则停止。否则用 代vi转回（2）。vP( vi )min T(vi) 2022-6-731例例1212 用Dijkstra算法求图8-34中v1点到v8点的最短路。 图 8-34 v1 v2 v3 v4 v5 v6 v7 v8 4 4 4 4 5 5 5 6 6 7 7 1 9 解：解：(1)首先给v1以P标号，P(v1)=0，给其余所有点T标号，T(vi)=+ (i=2,8) (2)由于(v1,v2),(v1,v3)边属于E,且为T标号,所以修改这两个点的标号：T(v2) = min T(v2), P(v1) + l12 = min + ,0 + 4 =4 T(v3)
30、 = min T(v3), P(v1) + l13 = min + ,0 + 6 =6 (3) 比较所有T标号,T(v2)最小,所以令P(v2) = 4。 (4) v2为刚得到P标号的点,考察边(v2,v4),(v2,v5)的端点v4,v5。T(v4) = min T(v4 ), P(v2) + l24 =min + ,4+5=9T(v5) = minT(v5),P(v2) +l25= min+ ,4+4=8 (5)比较所有T标号,T(v3)最小,所以令P(v3)=6。 (6)考虑点v3，有 2022-6-732T(v4) = min T(v4), P(v3) + l34 = min 9, 6
31、 + 4 =9T(v5) = min T(v5), P(v3) + l35 = min 8, 6 + 7 =8(7) 全部T标号中,T(v5) 最小,令 P(v5) = 8(8) 考察 v5T(v6) = min T(v6), P(v5) + l56 = min +, 8 + 5 =13T(v7) = min T(v7), P(v5) + l57 = min +, 8 + 6 =14(9)全部T标号中,T(v4)最小,令P (v4) = 9(10)考察v4，T(v6) = min T(v6), P(v4) + l46 = min 13, 9 + 9 =13T(v7) = min T(v7),
32、P(v4) + l47 = min 14, 9 + 7 =14(11)全部T标号中,T(v6)最小,令P (v6) = 13(12)考察v6，T(v7) = min T(v7), P(v6) + l67 = min 14, 13 + 5 =14T(v8) = min T(v8), P(v6) + l68 = min +,13 + 4 =17(13)全部T标号中,T(v7)最小,令P (v7) = 14(14)考察v7 ,T(v8) = min T(v8), P(v7) + l78 = min 17,14 + 1=15 2022-6-733(15)因只有一个T标号T(v8),令P(v8)=15,
33、计算结束。全部计算结果见图8-35。 v1到v8之最短路为v1 v2 v5 v7 v8 路长p(v8)=15 ，同时得到v1 点到其余各点的最短路。 图 8-35(0) v1v2 (4)v3 (6) v4 (9) v5 (8) v6 (13) v7 (14) v8 (15) 4 4 4 4 5 5 5 6 6 7 7 1 9Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。这从一个简单例子就可以看到，图8-36中，我们按Dijkstra算法得P(v1)=5为从vsv1的最短路长显然是错误的, 从vs v2 v1只有3。 5 v2 vs v1 8 -5 图 8-3620
34、22-6-734二、逐次逼近算法二、逐次逼近算法本算法可用于网络中有带负权的边时，求某指定点到网络中任意点的最短路。算法的基本思路算法的基本思路：如果v1到vj的最短路总沿着该路从v1先到某一点vi，然后再沿边(vi,vj)到达vj，则v1到vi这条路必然也是v1到vi的最短路。若令P1j表示从v1到vj的最短路长，P1i为v1到vi的最短路长，则必有下列方程：),.,2 , 1(:,)(min1) 1 (111njlPlPPjjijiij开始时令用迭代法解这个方程即用v1到vj 的直接距离做初始解，若v1与vj 间无边，则记v1, vj间的最短路长为+ 。从第二步起，使用迭代公式.),.,2
35、 , 1(,),.,2 , 1(,.)3 , 2(min1)(1)1(1)(1)(1)1(11到各点的最短路长即为则停止步若出现当进行到第求vnjPnjPPtPklPPtjtjtjkjijkiikj2022-6-735例13 求图8-37中v1点到各点的最短距离。v2v5-1-3v1v3v4v6v7v82-2-344423567图 8-37)1(18)1(17)1(16)1(15)1(14)1(13)1(12)1(11, 3, 5, 2, 0:PPPPPPPP初始条件为解2,3,5 , 02 , 20min,min0,3,5 ,2 , 00min,min:82)1(1842)1(1432)1(
36、1322)1(1212)1(11)2(1281)1(1851)1(1541)1(1431)1(1321)1(1211)1(11)2(11lPlPlPlPlPPlPlPlPlPlPlPP第一轮迭代)2(18)2(17)2(16)2(15)2(14)2(1311630PPPPPP类似可得：可以看出P1j(2)表示从v1点两步到vj的最短路长。全部计算过程可用表8-1表示。2022-6-736表表 8-1（表中空格为（表中空格为+迭代进行到第六步时，发现P1j(6)= P1j(5)(j=1,8) 则停止。表中最后一列数字分别表示v1点到各点的最短路长。如果需要知道v1点到各点的最短路径,可采取“反向
37、追踪”的办法。2022-6-737如需要求出v1点到v8点的最短路径,已知P18=10而P18= minP1i+li8,在表中寻求满足等式的vi点，易知P16+l68=10,记下(v6, v8)再考查v6 ,由于P16=6,而6=0+6= P13+ l36记下(v3, v6)考查v3, P13=0而0=2+(-2) = P12+ l23，记下(v2, v3)所以由v1到v8的最短路径为 v1 v2 v3 v6 v8 由于递推公式中P1j(k)的实际意义为从v1到vj点、至多含有k-1个中间点的最短路权，所以在含有n个点的图中，如果不含有总权小于零的回路，求从v1点到任一点的最短路权，用上述算法
38、最多经过n-1次迭代必定收敛。显然如果图中含有总权小于零的回路，最短路权没有下界。2022-6-738例例1414 设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。若已知设备在各年的购买费及不同机器役龄时的残值与维修费，如表8-2所示 第1年 第2年 第3年 第4年 第5年 购买费 11 12 13 14 14机器役龄 01 12 23 34 45 维修费 5 6 8 11 18 残 值 6 3 2 1 0解：解： 把这个问题化为最短路问题用点vi表示第i年年初购进一台新的设备，虚设一
39、个点v6，表示第五年年底。边(vi ,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底)。2022-6-739边(vi,vj)上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用（可由表8-2计算得到）。例如(v1,v4)边上的28是第一年初购买费11加上三年的维修费5,6,8,减去3年役龄机器的残值2； (v2,v4)边上的20是第二年初购买费12减去机器残值3与使用二年维修费5,6之和，见图8-38。图 8-38v6v1v2v3v4v521 1213141515202922411928304059 第1年 第2年 第3年 第4年 第5年 购买费
40、11 12 13 14 14机器役龄 01 12 23 34 45 维修费 5 6 8 11 18 残 值 6 3 2 1 0这样设备更新问题就变为：求从v1 到v6的最短路问题，计算结果表明：v1 v3 v6为最短路，路长为49。即在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。2022-6-740例例1515 已知某地区的交通网络如图8-39所示，其中点代表居民小区，边表示公路，lij为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？解解 ：这是个选址问题，实际要求出图的中心，可以化一系列求最短路问题。先求出v1到其它各点的最
41、短路长dj，D(v1)=max(d1, d2, d7),表示若医院建在v1 ，则离医院最远的小区距离为D(v1) 。v1v2v3v4v5v6v730202030151815图 8-396025再依次计算v2, v3, v7到其余各点的最短路，类似求出D(v2) ,D(v3), D(v7). D(vi) (i=1,7)中最小者即为所求，计算结果见表8-3。2022-6-741表表 8-3 v1 v2 v3 v4 v5 v6 v7D(vi)v1 0 30 50 63 93 45 60 93v2 30 0 20 33 63 15 30 63v3 50 20 0 20 50 25 40 50 v4 6
42、3 33 20 0 30 18 33 63 v5 93 63 50 30 0 48 63 93 v6 45 15 25 18 48 0 15 48 v7 60 30 40 33 63 15 0 63由于 D(v6) =48最小，所以医院应建在v5 ，此时离医院最远的小区（v6）距离为48。2022-6-742三、三、Floyd 算法算法此法可直接求出网络中任意两点间的最短路。为计算方便,令网络的权矩阵为D=(dij)nn,lij为vi到vj的距离。其它当其中Evvldjiijij),(算法基本步骤：输入权矩阵D(0)D计算D(k)(dik(k)nn(k=1,2,n)其中dij(k)mindij
43、(k-1),dik(k-1)+dkj(k-1)D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。2022-6-743例例1616 求图8-40所示的图中任意两点间的最短路。 图8-40中有四条无向边，每条均可化为两条方向相反的有向边。则54321)0(0442406282032210052150vvvvvDDv1v2v3v4v50442402820322052150)1 (D 由于dij(1)=mindij(0),di1(0)+d1j(0)表示从vi到vj点或直接有边或借v1点为中间点时的最短路长。圆圈中元素为更新的元。6v1v2v3v4v522221445103图 8-
44、408000 , 0min,min,min)0(11)0(11)0(11)1(11)1()1()1()(ddddddddkkjkikkijkij550 , 5min,min,min)0(12)0(11)0(12)1(12)1()1()1()(ddddddddkkjkikkijkij1 10 , 1min,min,min)0(13)0(11)0(13)1(13)1()1()1()(ddddddddkkjkikkijkij220 , 2min,min,min)0(14)0(11)0(14)1(14)1()1()1()(ddddddddkkjkikkijkij0 ,min,min,min)0(15)
45、0(11)0(15)1(15)1()1()1()(ddddddddkkjkikkijkij6 15 ,10min,min,min)0(13)0(21)0(23)1(23)1()1()1()(ddddddddkkjkikkijkij725 ,min,min,min)0(14)0(21)0(24)1(24)1()1()1()(ddddddddkkjkikkijkij752 ,min,min,min)0(12)0(41)0(42)1(42)1()1()1()(ddddddddkkjkikkijkij3 12 , 6min,min,min)0(13)0(41)0(43)1(43)1()1()1()(d
46、dddddddkkjkikkijkij42, 4min,min,min)0(14)0(51)0(54)1(54)1()1()1()(ddddddddkkjkikkijkij2022-6-7440442403252032276052100442403722032276052150)3()2(DDDij(2) 与Dij(3)分别表示从vi 到vj最多经中间点v1 ,v2与v1 ,v2, v3的最短路长。由于Dij(5) 表示从vi点到vj点，最多经由中点v1 ,v2, ,v5,的最短路长. 所以D(5)就给出了任意两点间不论几步到达的最短路长。725 ,min,min,min)1(25)1(12)
47、1(15)2(15)1()1()1()(ddddddddkkjkikkijkij523 , 8min,min,min)1(25)1(32)1(35)2(35)1()1()1()(ddddddddkkjkikkijkij752 ,min,min,min)1(21)1(52)1(51)2(51)1()1()1()(ddddddddkkjkikkijkij431 , 5min,min,min)2(32)2(13)2(12)3(12)1()1()1()(ddddddddkkjkikkijkij651 , 7min,min,min)2(35)2(13)2(15)3(15)1()1()1()(dddddd
48、ddkkjkikkijkij633 , 7min,min,min)2(32)2(43)2(42)3(42)1()1()1()(ddddddddkkjkikkijkij624 , 7min,min,min)2(31)2(53)2(51)3(51)1()1()1()(ddddddddkkjkikkijkij0442640362520322605621400442640362520322760562140)5()4(DD642 , 7min,min,min)4(54)4(25)4(24)5(24)1()1()1()(ddddddddkkjkikkijkij2022-6-745如果希望计算结果不仅给出
49、任意两点的最短路长，而且给出具体的最短路径，则在运算过程中要保留下标信息，即 dik+dkj=dikj 等。如例中，D(1)的d23(1)=6是由d21(0)+d13(0)=5+1=6得到的，所以d23(1)可写为6213，而d35(2)=5是由d32(1)+d25(1)=3+2=5得到的，所以d3 5( 2 )可以写为53 2 5，而D(3)中的d1 5( 3 )=6，是由d13(2)+d35(2)=1+5=6得到的，而d35(2)=5325，所以d15(3)可写为61325等等。04426403625203226605621405453525314541341324132534323125
50、2542132113251413132)5(D2022-6-7468-4 8-4 最大流问题最大流问题一、最大流有关概念一、最大流有关概念如果把图8-41看做输油管道网,vs为起点,vt为终点,v1, v2, v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大。所谓最大流问题就是：。vtv1v2v3v4vs图 8-4144324222133定 义定 义 2 0 设 有 向 连 通 图G=(V,E)，G的每条边(vi,vj)上有非负数cij称为边的容量，仅有一个入次为0的点vs称为发点（源），一个出次为0的点vt称为收点(汇),其余点
