《运筹学06图与网络分析资料课件.ppt》由会员分享，可在线阅读，更多相关《运筹学06图与网络分析资料课件.ppt（115页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、碗罗滓孰河揽斤醒垢勿茧她灾栋疹闯盅应晌扮匹喀救讫清浊厩销赐腿肯沂运筹学06图与网络分析运筹学06图与网络分析ABCD图与网络分析图与网络分析Graph Theory and Network Analysis1.图的基本概念Basic Concepts of Graph2.最小支撑树问题The Minimal Spanning Tree Problem3.最短路问题The Shortest Route/Path Problem4.最大流问题The Maximal Flow Problem5.最小费用最大流The Minimal Cost&Maximal Flow6.中国邮递员问题Chinese
2、Postman Problem7.网络计划技术Network Planning Technology且啪岳茂渴测呈恭砰恤分蛮墨牢笋橇赶缸伯俩曰应混恰澜辈丢芒藏响轧靡运筹学06图与网络分析运筹学06图与网络分析1 图的基本概念v案例导引v图论中的图v图的矩阵描述味仅刑汤遵停薄壕蓑戌眠嚏淡欲杖苏啤骏丝代贩拘稳盲诡匡礼泉馁芜歧乐运筹学06图与网络分析运筹学06图与网络分析案例导引v图论是运筹学的一个重要分支，对其最早的研究可以追溯到著名的哥尼斯堡七桥问题(Konigsberg Bridges Problem)。18世纪，欧洲的哥尼斯堡城有一条流经全城的普雷戈尔河，河的两岸与河中两个小岛及两岛之间有七
3、座桥彼此相通(如左图)。v当时人们关心这样的问题，即从陆地A,B,C,D中的任意地方出发，能否通过每座桥一次且仅通过一次，就能返回原出发地。娟使迄吻域帛切肾统跪哉乳奉箍仟穴惟峨刨赋炉萍食函颠皑胎离遏崇松殃运筹学06图与网络分析运筹学06图与网络分析v1736年，瑞士数学家欧拉(E.Euler,1707-1783)当时正在圣彼得堡科学院工作，为俄罗斯女皇凯瑟琳服务。欧拉将这个问题抽象化，用含有4个点7条边的图形表示此问题(如右图)，发表依据几何位置的解题方法的论文，有效地解决了哥尼斯堡七桥问题。标志着欧拉创立了一个数学分枝，即后来人们所熟知的拓扑学(Topology)。v图论的第一部专著是匈牙利
4、数学家O.Konig于1936出版的有限图与无限图的理论。刘峪肾豹届营测联握克友亦速袱闷氦钨给睫眯粘惯砌读缚诸赏左背梗烃曲运筹学06图与网络分析运筹学06图与网络分析ABCDv哥尼斯堡七桥问题：在图中找一条经过每边一次且仅一次的路欧拉回路。ADBC由点和边组成由点和边组成赖卷臻隅梗汗儡刃氨谴厌言铁织唾涧幅莎茬表迅噶涤磐叶赖暂蠕款除袖佰运筹学06图与网络分析运筹学06图与网络分析v环球旅行问题在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。v中国邮路问题在图中找一条经过每边的最短路类似带权的欧拉回路。v货郎担问题在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。食餐资鹿佃矩梦啦劳
5、佳翻对谨味师碍棺所搂门席朝唬滚丽抢老猎毖掸说迁运筹学06图与网络分析运筹学06图与网络分析图论中的图v图论中的图图论中的图：人们只关心有多少个点，这些点可以形成多少条边，它们的连接形式如何；不关心这些点的地理位置，边的长短和形状。秉肯今经郑跨捉袋譬拂崇句嗣容耐膜缄亨需谢惑脆蔬叙汐焚忽思冗旋瑰刃运筹学06图与网络分析运筹学06图与网络分析v设V=v1,v2,vn是n个元素的非空集合，E=e1,e2,em是m个元素的集合，若对于任意ejE，均有vs,vtV与之对应，则称VE为图图，记为G=(V,E)。v在G中，称vi为G的顶点顶点，ej为G的边边，并记ej=(vs,vt)=(vt,vs)，称vs,
6、vt是ej的端点端点，ej是与vs,vt关联的边关联的边，称vs,vt为邻接的点邻接的点。v如果图中某一边的两个端点相同，则称为环环。如果图中的两边(或多边)具有相同的一对端点，则称为多重边多重边(或平行边)。无环和无多重边的图称为简单图简单图。副楼鹊陕悟品汲奏神太瘪躲考抹粕渴殃回炙粒罚秤幻峡圈便奔怕拌删苏锌运筹学06图与网络分析运筹学06图与网络分析 例1：用图符号表示右图。解：(1)图G=(V,E)(2)V=v1,v2,v3,v4(3)E=e1,e2,e7，其中e1=(v1,v2)=(v2,v1)多重边e2=(v1,v2)=(v2,v1)多重边e3=(v2,v3)=(v3,v2)e4=(v
7、3,v4)=(v4,v3)e5=(v1,v4)=(v4,v1)e6=(v1,v3)=(v3,v1)e7=(v4,v4)环穆恋彩俄货傻赦并脐仪祸先雏伯枕舱嘿都关卫彰悸何肾请了掖岗洽氮劲彝运筹学06图与网络分析运筹学06图与网络分析v与顶点v相关联的边数称为v的次数次数，记为d(v)。次数为零的点称为孤立点孤立点；次数为奇数的点为奇点奇点；次数为偶数的点称为偶点偶点；次数为1的点为悬挂点悬挂点；与悬挂点关联的边称为悬挂悬挂边边。v右图中各点的次数：d(v1)=4偶点d(v2)=3奇点d(v3)=4偶点d(v4)=1悬挂点d(v5)=0孤立点毛酪耘伪菱闸馅溃某滦窟坑葫瞥蝎架哥膊指赖或毫拘魄节行臣枕恬
8、蝴兄究运筹学06图与网络分析运筹学06图与网络分析v定理1 任一图中顶点次数之和等于边数的二倍，即d(vi)=2m。证明：次数表示与顶点相关联的边数，同一条边有两个邻接的点，即每一条边被邻接的点合计计算了2次，故次数之和等于边数的二倍。v定理2 任一图中奇点的个数必为偶数。证明：若奇点的个数是奇数，则这些顶点的次数之和必为奇数，所有顶点次数之和就是奇数，这与定理1矛盾。故奇点的个数必为偶数。炯悉贫补细赣骏风堪殉碱砒讯陋咨夸铭拽逃熏旁田撑肋艘寝贪霸悟缚嘻豢运筹学06图与网络分析运筹学06图与网络分析v在图G中，从一个顶点出发，经过边、点、边、点、，最后到达某一点，称为G中的一条链链，用经过这条链
9、的顶点或边表示。如上图中有一条链=(v1,v2,v3,v4)=(e2,e4,e6)。v若链中的顶点均是不同的，则称为初等链初等链；若链中所含的边均不相同，则称为简单链，简单链，也称为通路，通路，简称路路。上述链是初等链，也是简单链，是通路。蚁笔搏别煎设炽焉徐浪益袄丈硷家矩浩渍军亲面浸母楼遍柠蓬莲免妮洗碾运筹学06图与网络分析运筹学06图与网络分析v链=(v1,v2,vn)中，若v1=vn，则称此链为一个圈圈。若圈中的点都是不同的，则称为初初等圈等圈；若圈中所含的边均不相同，则称为简简单圈单圈。v在一个图中，若任意两点之间至少存在一条链，则称该图为连通图连通图，否则为不连通图不连通图。若有图G=
10、(V,E)，取其全部或部分顶点V1，再取其全部或部分边E1，这里V1非空，且E1中的端点都在V1中，则称图G1=(V1,E1)为图G的子图子图。睛免凸诧葛赚馈朽趾性捌笔煮侈蛮匣赣人舞奸提外丫涛语恃奎消唉婉度竟运筹学06图与网络分析运筹学06图与网络分析v设V=v1,v2,vn是n个元素的非空集合，A=a1,a2,am是m个元素的集合，若对于任一ajA，均有有序对(vs,vt)与之对应，则称VA为有向图有向图，记为D=(V,A)。称vi为顶点，aj为弧弧，记为aj=(vs,vt)，在不至于混淆时也称为边。v在有向图D中，从一个顶点出发，顺着弧的方向，经过弧、点、弧、点、，最后达到某一点，称为D中
11、的一条单向链单向链或通路通路，简称路路，用经过这条单向链的顶点(或弧)表示。测则柯缘证芽柿禽囤诬汉痈无菱疤然嘉石里骋运屏刺监漏嗽涉祖修村远废运筹学06图与网络分析运筹学06图与网络分析v在有向图中，顶点次数分为入次d-(vi)和出次d+(vi)，入次入次是以该顶点为终点的边数，出次出次是以该顶点为起点的边数。页蹲谭跪肾宗凯棉亲酞获怕淋吴湃磐敝届徘骄翟报铺岸镭唁镀尽熟掸糜降运筹学06图与网络分析运筹学06图与网络分析v例2：用符号表示右边的有向图。D=(V,A)，其中V=v1,v2,v3,v4,v5A=a1,a2,a3,a4,a5,a6,a7a1=(v1,v5)a2=(v5,v4)a3=(v1,
12、v4)a4=(v3,v1)a5=(v1,v2)a6=(v2,v3)a7=(v1,v4)v1v2v3v4v5a1a2a3a4a5a6a7d-(v1)=1；d+(v1)=3d-(v2)=1；d+(v2)=1d-(v3)=1；d+(v3)=2d-(v4)=3；d+(v4)=0d-(v5)=1；d+(v5)=1琳鞍耸估姆填逃祷介锅夕芍皿界堂揉骇灾炉祝蚜鼻鞍埠蓬慨昂堂允薯诚犬运筹学06图与网络分析运筹学06图与网络分析v如果对于给定的图G=(V,E)的任意一边eE，有一实数W(e)与之对应，则称G为赋权图赋权图，称W(e)为边边e的权的权。v赋权图的应用比较广泛，如交通图中，权数可以是两点之间的单位运费
13、、运能等；在工程网络图中，权数代表工序的时间。v设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权通路的权。v对于一个有向图也可以定义权数使之成为有向有向赋权图赋权图。嗓戚日巡洗成岸评楔铬资她驹散冒粤王宵热甥撞倦泛结永埃讳动咀户皂疼运筹学06图与网络分析运筹学06图与网络分析v一个连通图连同定义在其边集上的实数W(e)一起称为一个网络网络。v若一个网络的每条边均有方向，称为有向网有向网络络；每一条边均无方向，称为无向网络无向网络；若有些边有向，有些边无向，则称为混合网络混合网络。诲爽磷团粮与大些氟弹鄂并哇龋抵北缅乃嵌菇熔牵忻参纬尹苏履枢绢帚柜运筹学06图与网络分析运筹学06图与
14、网络分析图的矩阵描述v无权图的邻接矩阵表示两顶点之间有边相连的记为1，无边相连的记为0，对角线位置数据记为0，这样就得到无权图的邻接矩阵，该矩阵一定是对称矩阵。v1v2v3v4v5终点v1v2v3v4v5起点v101100v210011v310001v401001v501110镐荒玖狞田庞激改片胡栓螟涵霄胰锦炬歇侧瓷缩吼谤驰漫吼陆董该炊瀑醇运筹学06图与网络分析运筹学06图与网络分析v赋权无向图的邻接矩阵表示两顶点之间有边相连的，写上其权数，无边相连的记为，对角线上的数字为0。赋权无向图对应的矩阵也是对称的。终点v1v2v3v4v5起点v1032 v23054v3208v4502v54820v
15、1v2v3v4v5423258妮吨斧减邦弘修站帛榴断搂漆毅契舀宵铰涡烂寺眼泵贾领镀豆储藩仔官将运筹学06图与网络分析运筹学06图与网络分析v赋权有向图的邻接表示矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为。终点v1v2v3v4v5起点v1032 v2054v3608v4 02v5 0v1v2v3v4v54232586植梆贾耪围俄暑贝窘虹吞砸芽多尿胆板蜀就候黑湿尘久搽拂劫鞠晃坐莉濒运筹学06图与网络分析运筹学06图与网络分析2 最小支撑树问题v树及其性质v图的支撑树(生成树)v最小支撑树问题v根树及其应用诈绪侗阳睬矛徐劣蛛
16、蠕舜推景乞煤屡崎二檬隔占吟锤送碧摆豪峰角啤赛离运筹学06图与网络分析运筹学06图与网络分析树及其性质v树在现实中随处可见，如电话线架设、比赛程序、组织结构等。v树：连通的无圈的无向图称为树。知匹墒毖倾吻筋猾漏孝桂刀巧狮哟稽莹症溯掩佬霸脐垦邓判杜奴掷麓消膳运筹学06图与网络分析运筹学06图与网络分析v树的性质v图G=(V,E)，p个点、q条边，下列说法是等价的(1)G是一个树(2)G连通，且恰有p-1条边(3)G无圈，且恰有p-1条边(4)G连通，但每舍去一边就不连通(5)G无圈，但每增加一边即得唯一一个圈(6)G中任意两点之间恰有一条链(简单链)离母液李旱孺兄孰碑稚赎邢硼甭奋兴臆店涵神扁壶响黄
17、肃掇按梯郑挞恭售运筹学06图与网络分析运筹学06图与网络分析图的支撑树(生成树)v定义：设图T=(V,E)是图G=(V,E)的支撑子图，如果T是一个树，则称T是G的一个支撑树。v定理5：图G=(V,E)有支撑树的充分必要条件是G是连通的。慨硬馏碰锚奎鹏体戚讼冒赁晕蟹儡牲臂泡斋蛛陡饿墟川箭伦刊抖硕蝴布民运筹学06图与网络分析运筹学06图与网络分析v找图中生成树的方法求支撑树的破圈法学证砰宵耙瞒侨蒂集暖抠摔坑痰锣著娘拇馁绢八晾图隘乙洗落撤诀漱舱睦运筹学06图与网络分析运筹学06图与网络分析v找图中生成树的方法求支撑树的避圈法深探法广探法氯挣溅惺梭蕉坝巡惧允顶囚镁浙引恬谓燎械凸罚有续赴咖攘骏巳靴坤椽
18、倾运筹学06图与网络分析运筹学06图与网络分析最小支撑树问题v赋权图(网络)：给定图G=(V,E),对G中的每一条边(vi,vj)，相应地有一个数wij，则称这样的图为赋权图。wij 称为边(vi,vj)上的权。v支撑树的权：若T=(V,E)是G的一个支撑树，E中的所有边的权之和称为支撑树的权，记为w(T)：w(T)=wij(其中(vi,vj)T)朴黎曾充箱爹堵华恼绝予玛位奄帜嗡斋洗夜壶力羚飘场日孪肛岭耻棕澄吻运筹学06图与网络分析运筹学06图与网络分析v满足w(T*)=min(w(T)的树T*称为最小支撑树(最小树)。v求最小树的方法求最小树的避圈法求最小树的破圈法硼教孪惟丑拟捍搓硫驯了阑冉
19、迎浪喧羌淬漆忆乞丸只深乘秋度末璃寻擒塑运筹学06图与网络分析运筹学06图与网络分析根树及其应用v有向树中的根树在计算机科学、决策论中有很重要的应用v有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树有向树。v根树：有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树根树(又称外向树外向树)。根树中入次为0的点称为根根。根树中出次为0的点称为叶叶。入次和出次均大于0的点称为分枝点分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次层次。泼拧舞辞匙馒疽肛儿瞳象卷樊婿恰丢翁恭潮粮宝肄蔗糕停毁申膏奏汹沾穴运筹学06图与网络分析运筹学06图与网络分析v
20、在根树中，若每个顶点的出次小于或等于M，称这棵树为M叉树叉树。v若每个顶点的出次恰好等于M或者零，则称这棵树为完全完全M叉树叉树。v当M=2时，称为二叉树二叉树、完全二叉树完全二叉树。缆遏化谬奈叉般有窄墩讨慢涸才绢碱闺贺木孔偶朝掏驶呀熟焙撅硬涉倡柔运筹学06图与网络分析运筹学06图与网络分析v如图所示的树是根树。其中根、分枝点、叶；各点层次都标注在树上。v这是一棵三叉树根叶分点枝第一层第三层第二层三叉树肘挨屁腹既蔑姐港奉啄院沽漱捣痕邀虎象单劣酱冯蹿旅滥梁拿绵罗咀铸纵运筹学06图与网络分析运筹学06图与网络分析v带权的二叉树T：令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)
21、为li(i=1,2,s)，这样二叉树T的总权数m(T)=pili。v满足总权数最小的二叉树称为最优二叉树最优二叉树(也称Huffman树)。vHuffman算法(D.A.Huffman最优二叉树算法)将s个叶子按权由小至大排序将二个具有最小权的叶子合并成一个分枝点，其权为两者之和，将新的分枝点作为一个叶子。转上一步，直到结束。段裸橙慨稗寒定吃畴茧磕娩龋畦镶胆帘娇滦颤颂藉嫌鸿煮湛想缄扮肠役浇运筹学06图与网络分析运筹学06图与网络分析v例3：s=6，其权分别为4,3,3,2,2,1，求最优二叉树。123243365牟她丸池汤戴辫炸戊哮晤贿抑间馈处矗纲鸦贝狭人似透小互亚培婴窗撩躲运筹学06图与网络
22、分析运筹学06图与网络分析123243396515123243396515弗孝趴刮县登革资穴尤抬广迷天厄稳孵管清滔雾悍涵搂厕铰络桩些毗仁槛运筹学06图与网络分析运筹学06图与网络分析v例4：最优检索问题。使用计算机进行图书分类。现有五类图书共万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？v解：构造一棵具有5个叶子的二叉树，其叶子的权分别为50,20,5,10,15。生成最优二叉树：C与D合并，之后与E合并，之后与B合并，之后与A合并。总权=5*4+10*4+15*3+20*2+50=195。分检过程：先将A类
23、分检出来，然后分检B，然后分检E，最后分检D、C。袖咕橇要酒术晓亮齿托娜秩莹严蜂涌寐勒赢落戏爪椽卷什渣隧科雾姥哪暂运筹学06图与网络分析运筹学06图与网络分析3 最短路问题v概述v最短路算法Dijkstra算法v最短路算法矩阵算法v最短路算法Floyd算法彦觅惯啄煎昨似射徘衬星帆俺耐捷扶新钢烬湘架沂粗竭炸合元淌琶扦堆侧运筹学06图与网络分析运筹学06图与网络分析概述v最短路问题最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。v最短路问题在实际分析中有广泛的应用，如管道铺设、运输路线选择、工厂布局等。v有些问题看起来与
24、地理方位无关，但通过适当转化也可以将其归结为最短路问题，如设备更新问题等。目朗企六叮突留茧挞瑶绪舌郑烯铁钙剂崎眺龟望相倡烛蜜行碰奄啼迷陈付运筹学06图与网络分析运筹学06图与网络分析v最短路问题的一般描述：对D=(V,A)，aij=(vi,vj)，w(aij)=wij，P是从vs到vt的路，定义路P的权是P中所有弧的权的和，记为w(P)。最短路问题则成为求w(P0)=min(w(P)|P)。路P0的权称为从vs到vt的距离，记为：d(vs,vt)。持滁城歌撰日梯祭失阐欲媳希合毅戴帆似粪瓦鬼绚喧快蜗囊卿潍削乏典约运筹学06图与网络分析运筹学06图与网络分析最短路算法Dijkstra算法v最短路的
25、标号算法是由E.D.Dijkstra于1959年提出的，也称Dijkstra算法，是目前公认的求解最短路问题的较好算法，但此算法要求网络中边的权wij0。脓蠢法吭衫膊沛浊茵殴踞般砷胞挎请遣鹰隆抿虽易毖禹警肪阻简睬饲踩吊运筹学06图与网络分析运筹学06图与网络分析vDijkstra算法步骤：(1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。(2)若已经计算出起点到若干点S=v1,v2,vi的最短距离，在找下一点时，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。(3)重复上述过程，直到终
26、点的标号被找到，则终止计算，找出最短路。扳举主迭脚苔电绢赏吐坟轿局群冕叛栽爆顷扬居复邹祝颇类滓辞爵呵俭密运筹学06图与网络分析运筹学06图与网络分析v例5：设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输路线。v4v2v1v3v6v5v714425316227欣吱皆畴桅吼代锐谗仟碘仪您昌菱膛椭溢掉霹泞臀数苗篡茂维倡略桥毛涧运筹学06图与网络分析运筹学06图与网络分析序号 与S关联边距离集合S标号(0)d(v1)=0v1d(v1)=0(1)(v1,v2)(v1,v3)k12=d(v1)+l(v1,v2)=0+1=1k13=d(v1)+l(v1,v3)=0+4=4v1,
27、v2d(v2)=1v1(2)(v1,v3)(v2,v3)(v2,v4)(v2,v5)(v2,v6)k13=d(v1)+l(v1,v3)=0+4=4k23=d(v2)+l(v2,v3)=1+2=3k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k26=d(v2)+l(v2,v6)=1+5=6v1,v2,v3d(v3)=3v2(3)(v2,v4)(v2,v5)(v2,v6)(v3,v6)k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k26=d(v2)+l(v2,v6)=1+5=6k36=d(v3)+l
28、(v3,v6)=3+1=4v1,v2,v3,v6d(v6)=4v3府良蝴捎守贼我惨谴瞎菇栋芯牌蛹穗掠忧鸟叙滥棉屈变姥蚊劫遵缀铭蓝赡运筹学06图与网络分析运筹学06图与网络分析序号 与S关联边 距离集合S标号(4)(v2,v4)(v2,v5)(v6,v5)(v6,v7)k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k65=d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4d(v4)=5v2(5)(v4,v5)(v2,v5)(v6,v5)(v6,v7)k45=d(v4)+l(v4,v5)=5
29、+2=7k25=d(v2)+l(v2,v5)=1+7=8k65=d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5d(v5)=7v4,v6(6)(v5,v7)(v6,v7)k57=d(v5)+l(v5,v7)=7+2=9k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5,7d(v7)=9v5v最短运输路线：(1)v1-v2-v4-v5-v7或(2)v1-v2-v3-v6-v5-v7v最短距离=d(v7)=9掘从绸贪窟片峙窝驴翌赣邵面回集氯诉措御屎钥为汽定笑辕貉翼刮猜偏曳运筹学06图与网络分析运筹学06图与网络分
30、析最短路算法Dijkstra算法(PT标号)v(1)对源vs标以永久P标号：P(vs)=0；对其他顶点标以临时T标号：T(u)=。v(2)检查所有从P标号顶点到T标号顶点的弧。重新计算所有T标号的顶点的值T(v)=min(T(v),P(u)+c(u,v)v(3)计算T(v)=min(T(i)，标号P(v)，记录对应uv(4)重复(2)-(3)，直到全部顶点为P标号。最短路采用反向追踪；最短距离=P(vt)。镐勿高耻婪咸步割娜芯类览华氧荚噪边盘息透拘锌梳释饮纵摆仔磺片斜捡运筹学06图与网络分析运筹学06图与网络分析k123456710*21*1433*25864584*355*271067*4,
31、61079*511 11111 11111 11111 11111 11111 11111 11111最短运输路线:(1)1-2-4-5-7;(2)1-2-3-6-5-7最短距离:d=9魔沈凶诚豫总辛冲猛孤炮窥访鲍檬瓷埠恍凛氧悸乞秀鸵骋九椭蒸蒜颂劈巴运筹学06图与网络分析运筹学06图与网络分析最短路算法矩阵算法v最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。v矩阵算法的基本思路与标号算法的基本思路一致。只不过一个标注在表上另一个标注在图上；标注在表上的便于计算机处理，标注在图上的直观蝇婪蛇板岿疡行骑猴琢爬麦琵炼抉敛瞳瓮旗崇膜帜萎惩剔酥购阎捎剔闺疽运筹学06图与网络分析运筹学0
32、6图与网络分析v矩阵算法的步骤：(1)将图表示成矩阵形式(2)确定起点行，标号为0，划去相应列(3)在已标号行且未划去的元素中，找出最小元素aij，圈起来，划去第j列，第j行标号aij，把第j行中未划去的各元素都加上aij(4)重复(3)，如果各行均已获得标号(或终点已经获得标号)，则终止计算。利用反向追踪，获得自起始点到各点的最短路；对应标号即为最短距离。狙阮厢窗号宙刑宵纫基琼驾噶垫汗奄疙踏页龄眠玛鳞烦隘满蛊日跟仁拍誉运筹学06图与网络分析运筹学06图与网络分析v例6：对上述例子利用矩阵算法求最短的运输路线。v解答：(1)先根据图完成矩阵表示。v1v2v3v4v5v6v7v1014v2102
33、475v34201v4402v572032v651306v7260霓粹酮禾畏蚁京磁愈匿恶仗撼校成你适要捌挖慷小懒刚谰位很巨踢涝焊纠运筹学06图与网络分析运筹学06图与网络分析v1v2v3v4v5v6v70v1014v2102475v34201v4402v572032v651306v7260v(2)找到起始点v1，第1行标号0，划去第1列摊绪涪疚滚靳冰缠赘汝史沥车柯装江椅桓募角栈猜蝗辱认啤勺饰剃选娶磨运筹学06图与网络分析运筹学06图与网络分析v(3)在已标号行(第1行)且未划去的元素中(1,4)，寻找最小的元素(即为a12=1)。完成下列4项：圈：将a12圈起来；划：划去第2列；标：第2行标号
34、1；加：第2行未划去的元素都加上1v1v2v3v4v5v6v70v10141v2102+14+17+15+1v34201v4402v572032v651306v7260频痴薯棱粘雅珐瓦溶蜗壤没徐沛驴哮稀惜渐畴绸呈突慧卑傀孩练挽万亨官运筹学06图与网络分析运筹学06图与网络分析v(4)重复(3)。在已标号行(第1-2行)且未划去的元素中(4,3,5,8,6)，寻找最小的元素(即为a23=3)。完成下列4项：圈：将a23圈起来；划：划去第3列；标：第3行标号3；加：第3行未划去的元素都加上3v1v2v3v4v5v6v70v10141v21035863v34201+3v4402v572032v651
35、306v7260丽炔秽秸披黎亥庞啮思针疏圃接级那韧帮霜济扬陆揉纵捍韭助受桂如届杭运筹学06图与网络分析运筹学06图与网络分析v(5)重复(3)。在已标号行(第1-3行)且未划去的元素中(5,8,6,4)，寻找最小的元素(即为a36=4)。完成下列4项：圈：将a36圈起来；划：划去第6列；标：第6行标号4；加：第6行未划去的元素都加上4v1v2v3v4v5v6v70v10141v21035863v34204v4402v5720324v6513+406+4v7260窿店扁仪抢漏济鄂凄邯爷吝信穷米堡前亿懦勺晋屋米俭虽忿虐阑仆州矗浴运筹学06图与网络分析运筹学06图与网络分析v(6)重复(3)。在已标
36、号行(第1-3,6行)且未划去的元素中(5,8,7,10)，寻找最小的元素(即为a24=5)。完成下列4项：圈：将a24圈起来；划：划去第4列；标：第4行标号5；加：第4行未划去的元素都加上5v1v2v3v4v5v6v70v10141v21035863v342045v4402+5v5720324v6517010v7260蝗寞脑久贬枉侩范充佃滥萌椭钵哈驴辫涧帛井眷神佬澡荤婆盈洒元砾眉担运筹学06图与网络分析运筹学06图与网络分析v(7)重复(3)。在已标号行(第1-4,6行)且未划去的元素中(8,7,7)，寻找最小的元素(即为a45=a65=7)。完成下列4项：圈：将a45和a65圈起来；划：划
37、去第5列；标：第5行标号7；加：第5行未划去的元素都加上7v1v2v3v4v5v6v70v10141v21035863v342045v44077v572032+74v6517010v7260干盂芦而峻蕾屋胺始衔俩馏度碟颓失寿升苫疾欺滨微痘潮怀倪乾住拢值幅运筹学06图与网络分析运筹学06图与网络分析v(8)重复(3)。在已标号行(第1-6行)且未划去的元素中(9,10)，寻找最小的元素(即为a57=9)。完成下列4项：圈：将a57圈起来；划：划去第7列；标：第7行标号9；加：第7行未划去的元素都加上9(全部划完)v1v2v3v4v5v6v70v10141v21035863v342045v4407
38、7v5720394v65170109v7260嚼寨注饶渍皂灿串候艺邓拧耙棕泻孤俩迫场户契给伍蔡涌惟拒恤哮低秉沏运筹学06图与网络分析运筹学06图与网络分析最短路算法Floyd算法v某些问题中，要求网络上任意两点之间的最短路，这类问题可以用Dijkstra算法依次改变起点的办法计算，但很繁琐。Floyd算法可以直接求取任意两点间最短路。vFloyd算法又称为弗洛伊德算法，插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。该法由Floyd于1962年完成(Robert W.Floyd:Algorithm 97:Shortest path,Comm
39、unications of the ACM,1962年第5卷第6期)。陡牡录踪拓叭镁魂与脓敌消辽死兽蒙饲咨痔言讥彩锅咀玉壹圃呸略希沁吱运筹学06图与网络分析运筹学06图与网络分析vFloyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。vFloyd算法的时间复杂度为O(n3)，空间复杂度为O(n2)。vFloyd算法，也有专业书籍称Floyd-Warshall算法(Floyd-Warshall Algorithm)。鲍笆爪检衣瘟医救呆瞧椅砾淌宰埠馆滩泥狸撮织闰岿比弘淫欣徽栓驮典拓运筹学06图与网络分析运筹学06图与网络分析v
40、Floyd算法(1)输入权矩阵D(0)=D=(dij)nn，dij取值为如果(vi,vj)E，则dij=lij为vi到vj的距离如果(vi,vj)不属于E，则dij=(2)计算D(k)=(dij(k)nn，其中dij(k)=min(dij(k-1),dis(k-1)+dsj(k-1)(3)D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。若D(p)=D(p-1)则也可结束。v迭代步长p根据公式2p-1n-12p估计池艇碱腥帧为亮滔超另铣噎依叭遂州楚睫泛骇笔秸鲜斧鸦仗巩货挖庚哑童运筹学06图与网络分析运筹学06图与网络分析例7：利用Floyd算法求上例中最短路。v1 v2
41、v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 014 v1 013585v2 102475v2 1024639v3 420 1v3 3206417D(0)=v4 402 D(1)=v4 5460254v5 72032v5 8642032v6 51306v6 5315305v7 260v7 974250111 1111111111111111111111111 111 111111111111111111111111v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 0135749v1 0135749v2 1024638v2 1024
42、638v3 3206416v3 3206416D(2)=v4 5460254D(3)=v4 5460254v5 7642032v5 7642032v6 4315305v6 4315305v7 9864250v7 9864250照扔藏获衫北残低刃胞充讼狡需帜嚼建辗创卵剐吻拈巡诺靴芝康耀高我愿运筹学06图与网络分析运筹学06图与网络分析v例8：若某地7个村庄之间的交通道路如图所示。旁边数字为各村庄之间道路的长度。试求各村之间的最短距离。12345672223344456771船舌相袄雾楞诱崎佬交烤衙欲卓敝筛馈喂宦勺嫌二载虱柠弟刻缝缓项剔淮运筹学06图与网络分析运筹学06图与网络分析解答034703
43、45711 13303243032458430574305569D(0)=72026D(1)=52502364520147452013710211563102642013896320111 1111111111111111111111 111 11111111111111111111103457810034578103032457303245743055684305568D(2)=5250235D(3)=525023574520137452013856310285631021078532010785320繁惑薪楼溢民叼陆伙雪痢寅喧祝旗噎果墟浑匠茅屋掷噬形膨谐喜祭柴绞忙运筹学06图与网络分析运筹
44、学06图与网络分析例9：用Floyd算法计算有向图的最短路12345678910728612122424565104626884奏妖酋厩毕套趾终欺告沤考算君办弯切另振容焉疤巾嘿递钞及锑接或排蓝运筹学06图与网络分析运筹学06图与网络分析若v1v4方向不变，则结果如下12345678910108862042301072408D(0)=560212604712058064962041050111111 111 111 111 111 111 111 111 111 111 111牺咨寻蠕罢荧祸煮麻衙藤可乡虑奇此瓣塘央锡芭佃贺可侨篱钮寞窃湿说痘运筹学06图与网络分析运筹学06图与网络分析123456
45、7891010886151010204141162731301072640812D(1)=56100286181660410871812140511981289064962960410175100111111 111 111 111 111 111 111 111 111 111 111率承焚鞭膀娇螺洞茎旬剂渣赫渭缔混桂碱皿裹胯梧舜塌刻洼俊肢努狠焰怕运筹学06图与网络分析运筹学06图与网络分析12345678910108861510101420182041411627131131301072156121040821121816D(2)=56101802861210616250134108718
46、221712130511982712218906492762129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111朴驰嚼涛叙握嵌沪异赃赞蓝映荒韶递蛊疮处去喂杏古慕殉违疡流雕彤崩叶运筹学06图与网络分析运筹学06图与网络分析12345678910108861510101420182041411627131131301072156121043943033821121816D(3)=5610180286121063135162501341087182217121305119827311221890649273162
47、129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111态讲船枕夫赃洋滋数派穴心植惫继叭抠鞋怖峰胡饮臻掣腋忙仙寇贱郭赤缅运筹学06图与网络分析运筹学06图与网络分析12345678910108861510101420182041411627131131301072156121043943033821121816D(4)=5610180286121063135162501341087182217121305119827311221890649273162129604102327221718510160111111
48、 111 111 111 111 111 111 111 111 111 111蚁憾豺晾许厄柜敛酬咖佐牲副蝎捶勺颅乘尿贰挟糊阂浪膜揖蝗枉壹斌笨怪运筹学06图与网络分析运筹学06图与网络分析若v1v4方向改变，则结果如下12345678910108818151010142018220041411627131131613010721561210461414021816121816D(4)=5246101802861210622303016250134108723182217121305119818262612218906491220206212960410282327221718510160111
49、111 111 111 111 111 111 111 111 111 111 111烬榔捂毕酥主要授聊绷贫仙刷赌纶帘氟邹汗态韵浊师什旺耸谍吉俘替凄抱运筹学06图与网络分析运筹学06图与网络分析若v4v1容量为-6，则结果如下1234567891010881815101014201828041411627131134120107214612104-622094481412D(4)=512610180286121061018181625013410871118191712130511986141412218906490886152960410162324221718510160111111 11
50、1 111 111 111 111 111 111 111 111 111甸枉待奖术力孤诬君尚轧背婶没劈聘馒霍煎宠妊细聘翌辅控庇懂陀坏忙舍运筹学06图与网络分析运筹学06图与网络分析4 最大流问题v基本概念v最大流算法1标号算法v最大流算法2改进标号算法v最大流算法3最小截集法v最大流算法4线性规划(Excel求解)突嚷漾竹巨妻腥爽掖确苹祥樱枝绩谢汽焰栽秩肪挚罐陛驼篷婿教蔑骂昨呕运筹学06图与网络分析运筹学06图与网络分析基本概念v给定一个有向图D=(V,A)，如果对于每一条弧a=(vi,vj)A，均有一个非负实数cij=c(vi,vj)=c(a)C与之对应，称c(a)为弧a的容量容量；v称V