第8章_图与网络分析

1、图与网络分析 (Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,中国邮路问题,最大流问题,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,引 言,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,引例2,左图是我国北京、上海

2、、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。,引例3,图的基本概念与模型,点：研究对象（车站、国家、球队）；,点间连线：对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果)。,对称关系：桥、道路、边界；用不带箭头的连线表 示，称为边。,非对称关系：甲队胜乙队，用带箭头的连线表示，

3、 称为弧。,图：点及边（或弧）组成。,注意：一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上不同。,一、图与网络的基本知识 （一）图与网络的基本概念,1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）,一个图是由点集 和 中元素的无序对的集合 构成的二元组，记为G =(V，E)，其中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。,例,图1,2、如果一个图是由点和边所构成的，则称其为无向图，记作G = (V，E)，连接点的边记作v

4、i , vj，或者vj , vi。,3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi , vj)。,图2,5、如果两个端点之间有两条 以上的边，称为多重边。,6、一个无环、无多重边的图称为简单图， 含有多重边的图称为多重图。,7、无向完全图每一对顶点间都有边相连的简单图； 有向完全图指每一对顶点之间有且仅有一条有向边的简单图。,4、一条边的两个端点是相同的, 称此边为环。,次为零的点弧立点,8、以点v为端点的边的个数称为点v 的次，记作,图中 d(v1)= 4，d(v6

5、)= 4（环计两次）,次为偶数的点偶点,次为1的点悬挂点,悬挂点的关联边悬挂边,次为奇数的点奇点,v7,定理1 任何图中，顶点次数的总和等于边数的2倍。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中： 以vi 为始点的边数称为点vi 的出次，用 表示； 以vi 为终点的边数称为点vi 的入次，用 表示； vi 点的出次和入次之和就是该点的次。,定理2 在任一图中，奇点的个数必为偶数。,一个称为始点（或发点），记作v1 ， 一个称为终点（或收点），记作vn ， 其余的点称为中间点。,9、在实际应用中，给定一个图G=（V，E）或有向图 D=（V，A），在V中指定两个点:,对每一条弧 ，对应

6、一个数 ，称为弧上的“权”。通常把这种赋权的图称为网络。,若链中所含的边均不相同，称为简单链 所含的点均不相同的链称为初等链 , 也称通路。,10、由两两相邻的点及其相关联的边构成的点边序列 称为链。,图的连通性,链：设图G=（V，E）中有一个点、边交替序列 v1 ,e1,v2,vn-1,en-1 ,vn，若ei=(vi,vi+1)，即这(n-1)条边把n个顶点串连起来，我们称这个交替序列为图G中的一条链，而称点v1,vn为该链的两个端点。,对于简单图链也可以仅用点的序列来表示。 如果一条链的两个端点是同一个点，则称它为闭链或圈； 如果一条链的各边均不相同，则称此链为简单链； 更若一条链的各点

7、、各边均不相同，则称该链为初等链。,图的连通性,最短链:网络中链上权值的和称为链的长度，以点v1,vn为端点的诸链中长度最短的链称为这两点的最短链。 连通图：如果图G=（V，E）中的任意两点都是其某一条链的两个端点，则称图G是连通图，否则，称图G是不连通的。,为不连通图，有两个连通分图组成,11、图中任意两点之间均至少有一条通路，则称此图 为连通图，否则称为不连通图。,图3,一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。,v4,v6,e2,e1,e3,e4,e5,e6,e7,e8,e9,e10,图4,对于网络（赋权

8、图）G=（V，E），其中边 有权 ，构造矩阵 ，其中：,设图G=（V，E）中顶点的个数为n，构造一个 矩阵 ，其中：,（二）图的矩阵表示,称矩阵A为网络G的权矩阵,称矩阵A为网络G的邻接矩阵,例,权矩阵,邻接矩阵,思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,分析：点表示项目，边表示两个项目有同一名运动员参加,目的：在图中找出点序列，使得依次排列的两个点不相邻，就找到了每名运动员不连续参加两项比赛的安排方案,A、C、B、

9、F、E、D,(不唯一),二、中国邮递员问题,一、欧拉回路与道路 定义 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。,推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。,具有欧拉回路的图称为欧拉图。,定理 一个多重连通图G是欧拉图的充分必要条件 是G中无奇点。,一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？,图论语言描述：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。

10、,二、中国邮路问题,中国邮路问题可转化为如下问题： 在连通图G=(V,E)中，求一个边集E1 E ，把G中属于E1的边均变为两重边得到图G*=G+E1，使其满足G*无奇点，且 最小。,奇偶点图上作业法,（1）每条边最多重复一次； （2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。,（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。,（2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。,（3）检查图中的每一个圈，如

11、果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。,奇偶点图上作业法,判定标准1: 在最优邮递路线上，图中的每一条边至多有一条重复边。 判定标准2 : 在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,例：求解下图所示网络的中国邮路问题，图中数字为该边的长。,l12+2 l23+2 l36+ l89+2 l78+l69+l14+2 l47=51,树：不含圈的连通图,什么是连通图：任意两点之间都有一条链相连。

12、什么是圈：起点和终点相同的链叫做圈。,已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。,二、树的基本概念,树的基本性质 任意两点之间有且只有一条链； 图是树的充要条件：任意两个顶点之间只有一条链； 若树有p个顶点，则共有q=p-1条边； 图是树的充要条件：连通图，边数=顶点数1。,树,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,如果G=（V，E）是一个无圈的连通图，则称G为树。,树中必存在次为1的点（悬挂点） 树中任两点必有一条链且仅有一条链； 在树的两个不相邻的点之间添加一条边，就得到一个圈； 反之，去掉树的任一条

13、边，树就成为不连通图； n个顶点的树有（n-1）条边。,树是无圈连通图中边数最多的，也是最脆弱的连通图！,1、连通且不含圈的无向图称为树。,树中次为1的点称为树叶，次大于1的点称为分支点。,任何树图中必存在次为1的点.,证明：,用反证法.,假设树图中不存在次为1的点.,又连通图中不存在孤立点，故树图中所有顶点的次2.,又可知与v2 , v3关联的边的其他端点v4 , v5，同样d(v4 )2, d(v5) 2，可继续一直往下推。,而图的顶点的总数是有限的，故最后必然回到前面的某一顶点，于是在图中出现了圈，这与树的定义产生了矛盾.,v1,v2,v3,v4,v5,不妨设d(v1)=2, 既v1有两

14、条关联边，,设关联边的其他两个端点为v2 , v3，而d(v2 )2, d(v3) 2，,悬挂点,悬挂边,一个图G 有生成树的充要条件是G 是连通图。,图的部分树（支撑树）,如果图G=（V，E）的部分图G=（V，E）是树， 则称G是G的部分树（或支撑树）。,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最小部分树（最小支撑树）。,点保留 边可去 仍是树 不唯一,思考：如何铺设电话线，使得电话线长度最少？,定义 树、生成树：,无圈的连通图称为树； 若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵生成树。

15、,图83(a)是一棵树，图83(b)是图81的一棵生成树。,v1,v1,图81,图83(a),图83(b),定理： 图G=（V，E）有生成树的充分必要条件为G是连通图。,生成树的寻求方法,在图中，每步选出一条边使它与已选边不构成圈，直到选够n-1 条边为止。,（）深探法 步骤：任取一点v，给v以标号； 若某点u已得标号i，检查其端点w是否已标号； 若端点w未标号，则给w以标号i+1;重复 若端点均已标号，则退到标号i1的点，重复。,(2) 广探法,任取一点v，给v以标号； 检查其所有端点wi是否已标号；若端点w未标号，则给所有wi以标号i+1; 对标号i+1的点重复。,（3）破圈法 在图中任意

16、取一个圈，从圈上任意舍弃一条边，将这个圈破掉；重复上述步骤，直到图中没有圈为止。,例：某乡有9个自然村，其乡间道路如下图，要求：以v0村为中心沿道路架设有线广播网络，应如何架设？,7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？,引例,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,分析：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：,连通图 图中有圈的话，从圈中任去掉一条边，余下的图仍连通,为什么？,求最小树的方法：,一、破圈法：在给定连通图G中，任取

17、一圈，去掉一条最大权边（若有两条或两条以上的权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图G的最小树。,二、避圈法：在给定连通图G中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图T即为所求的最小树。,最小树的应用： 电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计 电器设备线路网络（如数字计算机系统）的设计，使

18、得线路总长度最短 连接多个场所的管道网络设计,求最小树是在一个无向连通图G中求一棵最小生成树。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,方法一：破圈法,步骤： 1、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最大边，则任选其中的一条边去掉。 2、在余下的子图中，重复上述步骤，直至没有圈为止。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,

19、v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v

20、7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总权数=1+4+9+3+17+23=57,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,方法二：避圈法,避圈法：开始选一条最小权的边，在以后的每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，如果同时有几条都是最小权的边，则可从中任选一条。,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,

21、v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,总权数=1+4+9+3+17+23=57,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,破圈法求最小树：,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法求最小树：,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图6

22、1,例 用破圈法求图61的最小树。,图62,图62就是图61的最小部分树，最小树长为 w(T)=4+3+5+2+1=15。 当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。 最小部分树有可能不唯一，但最小树的长度相同,（2）避圈法：取图G的n个孤立点v1，v2， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图63,在图63中，如果添加边v1, v2就形成圈v1, v2, v4，这时就应避开添加边v1, v2，添加下一条最短边v3, v6。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等,M

23、in w(T)=15,最小生成树解法1（Kruskal算法）,避圈法： 这种方法每步从图中挑选一条边，满足：（1）它与已经选出的边不构成圈；（2）它是满足条件（1）的权最小的边，直到选够n-1条边为止。,9个顶点，8条边,避圈法另一种表述,先去掉图G的所有边，只留下顶点，每次放回一条权最小的边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。,9,4,8,2,3,3,3,7,9,1,4,2,3,3,1,6个顶点，5条边,最小生成树解法（2）,破圈法： 这种方法每步从图中任选一个圈，然后去掉该圈中权最大的边，直到图中没有圈为止。,1,4,1,2,1,3,1,4,4,5,5,3,2

24、,4,5,2,9个顶点，8条边,破圈法举例,9,4,8,2,3,3,3,7,9,1,9,4,8,2,3,3,3,7,9,1,6个顶点，5条边,破圈法举例,最小生成树的权= 9,/,/,/,/,例：分别用避圈法和破圈法求下图的最小部分树.,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,1. 避圈法,A,B,C,D,F,E,1,6,3,2,2,4,4,5,2,3,V,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,A,B,C,D,F,E,1,6,3,2,

25、4,4,5,2,3,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,分别用避圈法和破圈法求下图的最小部分树.,A,B,C,D,F,E,1,6,3,2,4,4,5,2,3,2. 破圈法,A,B,C,D,F,E,1,3,2,4,4,5,2,3,A,B,C,D,F,E,1,3,2,4,4,2,3,A,B,C,D,F,E,1,3,2,4,2,3,A,B,C,D,F,E,1,3,2,4,2,避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边；,加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min

26、C(T)=15,求最小树的方法：避圈法和破圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,得到最小树：,Min C(T)=15,(3) 矩阵求解算法,步骤1：构造一个矩阵，,T,步骤2：从矩阵中任一行开始，用T表明节点入树，划去该节点所在的列。,T,步骤3：在标T的行中选取最小元素，用方框表示，将对应的边入树，将新得到节点标T，划去所在列。,T,T,步骤4：重复步骤3。,T,T,T,矩阵计算方法,T,T,T,T,矩阵计算方法,T,T,T,T,T,矩阵计算方法,T,T,T,T,T,T,矩阵计算结果,6,8,3,5,7,2,3,4,8,根

27、树及其应用,定义 有向树：若一个有向图是一棵树，则称这个有向图为有向树。,定义 若有向树T恰有一个结点的入次为0，其余各点入次均为1，则称T为根树。,入次为0的点，称为根,出次为0的点，称为叶,其它顶点，称为分枝点,根到某顶点vi的道路长度，称为vi点的层次。,定义 在根树T中，若每个顶点的出次小于或等于m，则称T为m叉树。 若每个顶点的出次恰好等于m或零，则称T为完全m叉树。,当m=2时，称为二叉树、完全二叉树。,记二叉树各叶子的权为pi，根到各叶子的距离（层次）为 li 二叉树的总权数：,最优二叉树：满足总权最小的二叉树称为最优二叉树。 霍夫曼（D A Huffman)给出了一个求最优二叉

28、树的算法，又称霍夫曼树。,例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。,3,6,5,例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。,3,9,6,5,15,例：最优检索问题 用计算机进行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算次数最小？,算法步骤： 1.将s个叶子按权由小至大排序； 2.将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2；将新的分枝点作为一个叶子，合并，,解：构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15. 步骤如下

29、： 1.将5个叶子按权由小到大排序：5，10，15，20，50 2.找出二个最小权的叶子，合并成一个分枝点，其权为15；,依次，继续。,总权为：,分检过程是：先把A类50万册从总数中分检出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D、C分检出来。,例3：P235、例11,测试顺序,典例: 会议日程安排 某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下 会议A: 朱、马、牛、姬、江、姚 会议B: 朱、杨、张、江 会议C: 马、姬、侯、王、姚 会议D: 朱、姬、张 会议E: 杨、侯、王 会议F: 刘、杨、王、江、姚,每位领导每天最多只参加

30、一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议,A,B,C,D,E,F,会议日程安排如下: 上午 下午 第一天 会议A E 第二天 会议C B 第三天 会议D F,解: 用节点表示会议，若两个会议能安排在一天， 则用连线连接。,10名学生参加 6 门考试，每人每天最多考 1 门，A 必须第1天上午，F最后考，B安排在下午，三天结束。,学生 课程 A B C D E F 1 2 3 4 5 6 7 8 9 10 ,解：,做该图的补图,有八种药品，A、B、C 、D 、P 、R 、 S 、T要放

31、入储藏室保管，下列药品不 能储藏在同一室内： AR ，AC， AT ， RP ， PS ， ST ， TB ， BD， DC ， RS ， RB ， PD ， SC ， SD 问储存这八种药品需要多少间储藏室？,最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即： 最小。,(一) 狄克斯屈拉(Dijkstra)算法 适用于wij0，给出了从vs到任意一个点vj的最短路。,三 、最短路问题,算法步骤： （1）给始点vs以P标号 ，这表示从vs到vs的最 短距离为0，其余节点均给T标号， （2）设节点 vi

32、为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改： （3）比较所有具有T标号的节点，把最小者改为P标号， 即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,例：用Dijkstra算法求下图从v1到v6的最短路。,解：（1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,

33、1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,

34、2,X=1,2,4,min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2

35、,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,5,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1

36、,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,5,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,5,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=1

37、0,对有向图同样可以用标号算法： 例2 如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,v

38、8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,

39、4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,9,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,

40、8.5,9,二、最短路的矩阵算法 首先写出弧长矩阵D 第一步：划去矩阵D中第一列，并给第一行以标号0。,第二步：在已标号中未划去的元素中，寻找出最小的元素aij并圈起来，此时把第j列划去，同时给第j行标号i。并把第j行中未划去的各元素都加上aij。 第三步：如果各行均已获得标号，则停止，并利用标号倒向追踪，得到v1到各点的最短路。 若存在未标号行，返回第二步。,例 求v1到各点vj的最短路。,v1,v4,v2,v5,v3,v6,1,2,5,3,2,4,2,3,2,4,4,1,2,v1 v2 v3 v4 v5 v6 v1 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5

41、 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 v2 0 3 4 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 3+1 4+1 v3 2 0 5 1 v4 4 0 4 v5 2 3

42、0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 v4 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 4 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 4+2 v5 2 3 0 v6 2 2 0,v

43、1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 v3 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 1 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 1+4 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6

44、 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 v5 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 v6 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5 5 1 4 0 6 3 2 3 0 5 2 2 0,v1 v2 v3 v4 v5 v6 0 0 1 2 1 0 4 5 2 2 0 5

45、 5 1 4 0 6 3 2 3 0 6 2 2 ,v1到各点vj的最短路。,v1,v4,v2,v5,v3,v6,1,3,1,2,逐次逼近算法思想,该公式表明， P(1)1j中的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着k的增加而呈不增的趋势！,用于计算带有负权弧指定点v1到其余各点的最短路,逐次逼近算法基本步骤,例 计算从点v1到所有其它顶点的最短路,解：初始条件为,以后

46、按照公式 进行迭代。,直到得到 ，迭代停止。,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。 这里介绍Floyd在1962年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。,Floyd算法(路矩阵法)思想,考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一

47、个子网络D0，记,wij为弧（ vi，vj）的权。,在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为 ,则一定有,Floyd算法(路矩阵法)思想,再在D1中加入v2及D中与vi，vj，v1， v2相关联的弧，得D2，D2中vi到vj的最短路长记为 ，则有,Floyd算法(路矩阵法)思想,Floyd算法(路矩阵法)步骤,设有有向网络D=（V，A），其权矩阵为A=(aij)nn，,如下构造路矩阵序列：,则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。,令权矩阵A为初始路矩阵D（0），即令D（0）=A,2. 依次计算K阶路矩阵D（K）=（

48、d(k)ij）nn, k=1,2,n，,这里,路矩阵序列的含义,K阶路矩阵D（K） 其中的元素表示相应两点间可能以点v1、v2、vk为 转接点的所有路中路长最短的路的路长。,D（0） 其中的任一元素表示相应两点间无转接点时最短路路长。,一阶路矩阵D（1） 其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长；,为使计算程序化，转接点按顶点下标的顺序依次加入,n阶路矩阵D(n) 其中的元素d(n)ij就是vi到vj的可能以点v1、v2、vn为转接点的所有路中路长最短的路的路长。既是vi到vj的最短路的路长。,例 求如下交通网络中各对点间最短路路长。,该图的权矩阵为：,Floy

49、d算法(路矩阵法)算例,例 求如下交通网络中各对点间最短路路长。,Floyd算法(路矩阵法)算例,利用公式,发现第一行，第一列元素不变,利用公式,发现第二行，第二列元素不变,利用公式,发现第三行，第三列元素不变,利用公式,发现第四行，第四列元素不变,D(5)中的元素给出相应两点间 的最短路，其下标给出最短路 个顶点下标,比如：,6254,1,4,6,2,3,5,7,2,5,2,7,5,4,1,4,3,1,5,7,写出该网络图的距离矩阵，如下,1 2 3 4 5 6 7 1 0 2 5 4 2 2 0 2 7 3 5 2 0 1 5 3 D(0)= 4 4 1 0 4 5 7 5 0 1 5 6

50、 3 4 1 0 7 7 5 7 0 表示网络中任意两点之间直接到达的最短距离。,1 2 3 4 5 6 7 1 0 2 4 4 9 8 2 2 0 2 3 7 5 12 3 4 2 0 1 4 3 10 D(1)= 4 4 3 1 0 5 4 11 5 9 7 4 5 0 1 5 6 8 5 3 4 1 0 6 7 12 10 11 5 6 0,含义,表示： 网络中任意两点之间直接到达和经过一个中间点到达的最短距离。,矩阵计算法步骤二,dij(1)= min dir(0) + drj(0) i,j=1,2,n 1rn,1 2 3 4 5 6 7 1 0 2 4 4 8 7 14 2 2 0

51、2 3 6 5 11 3 4 2 0 1 4 3 9 D(2)= 4 4 3 1 0 5 4 10 5 8 6 4 5 0 1 5 6 7 5 3 4 1 0 6 7 14 11 9 10 5 6 0,含义,表示：网络中任意两点直接到达，经过一个、二个、三个中间点到达的最短距离。,dij(2)= min dir(1) + drj(1) i, j=1,2,n 1rn,1 2 3 4 5 6 7 1 0 2 4 4 8 7 13 2 2 0 2 3 6 5 11 3 4 2 0 1 4 3 9 D(3)= 4 4 3 1 0 5 4 10 5 8 6 4 5 0 1 5 6 7 5 3 4 1 0 6 7 13 11 9 10 5 6 0,含义,表示：网络中任意两点直接到达、经过一个、二个七个中间点到达的最短距离。,dij(3)= min dis(2) + dsj(2) i,j=1,2,n 1sn,对所有 i 和j, 若d(i, k)d(k, j)d(i, j)，则转第三步； 否则d(i,j)=d(i,k)d(k, j), path(i, j)= k，k = k 1，继续执行第三步。,Floyd 算法,问题：设简单赋权图 G = V, E 有 n 个顶点，