《《运筹学教程》第五版第五章图与网络分析课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学教程》第五版第五章图与网络分析课件.ppt（56页珍藏版）》请在三一办公上搜索。
1、第五章 图论与网络分析,肮餐鄂追文冷碾遥啮宣补洗巫陛倘潘雹砚辰劣誊记玄售钙擂稼湘灭讨衣帕运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,学习目标,腰讼职粘录股漳胯郧辆绑等俯付球拭雏起急胜恋罚久溪龙仕苑近押惑珍荣运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,图的基本概念,审君姓骆纹译霜柴猾宪反吗勺挨雨冲戎牢绊霍镍搜吭哄溉秋拯廊列痉徘腰运筹学教程胡云权第五版第五章图与网络分析运筹学
2、教程胡云权第五版第五章图与网络分析,哈密尔顿回路问题：环球旅行遊戏,欧拉回路：每边经过一次且仅一次的回路哈密尔顿回路：每个点经过一次且仅一次的回路,问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?,图的基本概念,辑番讨淹氧岛涅篓蓟刑泛宪洱残楼僵充父警鞭谦驻循晕焙院悄悉秸咒睦瓣运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,定义1：由点和边组成，记作G=(V，E)，其中 V=v1，v2，vn为结点的集合，E=e1，e2，em为边的集合。,点表示研究对象,边表示表示研究对象之间的特定关系,1.图,图的基本概念,注意：上面定义的图
3、区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。,V、E为有限集合，则为有限图，反之无限图。,匹冯偷贪拱莹鸿校持虏揣勉毡造肪蹈吹藐肢物畦叭勉沃硒渗语饰莆颜击柱运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,【例】图51，,边e=vi，vj，称vi和vj是边e的端点，vi和vj 两点相邻；边ex和ey有公共端点vi，称边ex和ey相邻，边ex和ey为点vi 的关联边；,v2和v4是边e6的端点，点v2、v4相邻。e6与e7共用顶点v4，e6与e7相邻，e6和e7为点v4的关联边。,图51,e
4、6可记作：,图的基本概念,端点，相邻，关联边,避抓孩雏雄擅抱阜懒补舜竞掐雇撼跑熄狂豌绘疫锤附廖黑儿毅侯恒暮腺誊运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图的基本概念,图51,环，多重边，简单图 一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e5,2、图的分类,定义2：无环、无多重边的图称作简单图。含有多重边的图为多重图。,楚汽肆拟簿愧超哺歧忿必唯阎洽涪指治洞屯续此诱环彤筛踏昆窍肝氮挝盲运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图,无向图，记作G=(V，E),有向图，记作D=(V，A)
5、,例1：哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,图的基本概念,景糙竹抹蘸抛痰献阉窥槛仰余锥解粉竹翻番逢蛙抄摹稀淘航从褪辑袒一透运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图的基本概念,定义3：每一对顶点间都有边相连的无向简单图，称为 完全图。有n个顶点的无向完全图记为Kn。,2、图的分类,定义4：图G=(V,E)的点集V可分为两个非空子集X、Y，即XY=V，XY=，使得E中每条边的两个 端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），有时记作G=(X,Y,E)。,橱锐稗垮贺膏雁吏誉烹馏娜寸笑丽运语弊盔抓兑毖鸡融
6、皖荔旺械莱秃牙剂运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图的基本概念,3、顶点的次,定义5：以点v为端点的边数叫点v的次（degree），记作deg(v)或d(v)。,图51,图5-1中，d(v1)，d(v3)=5，d(v5)=1。,次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。次为1的点称作悬挂点，连接悬挂点的边为悬挂边。图的次：各点的次之和。有向图中顶点的次？,定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点为偶数个。,书淆暑您拔肾瑶揣荡阶磨贴憋恫搞革糕言痕瞩妓夜减壳侈弟版衍诧诸示徒运筹学教程胡云
7、权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,4、子图、支撑子图,图G=(V,E)和G=(V,E)，若V V，E E，则称G 为G的子图。特别地，若V=V 且E E，则称G 为G的支撑子图。,G2为G1的支撑子图,图的基本概念,弘谁墩涎股亥匪痊羚吃曝淹汛檬尸埂陶仔父阂役恐秒纶革况赋袜侄机陈熏运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,5、赋权图（网络）,图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。,图的基本概念,犯桔漏猿米所腹抓悟割涂涎薪泣纸列瞎径嘛惮圆垒碾裸狗返耽框马携霹共运筹学教程胡云权第五版第五
8、章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,6、链与路、圈与回路,链,点边交错的序列,路,点弧交错的序列,回路,起点=终点的路,无向图：,有向图：,图的基本概念,没有重复点和重复边的链为初等链。初等圈,当耳隅趋泰哉援埃疡弯炊捐倚诬饼驱盏睦梢严珊氓搭站虚监秆出锨衬做渝运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,7、连通图,G1为不连通图，G2为连通图,例：,图的基本概念,明肉舌烤狈筹涂丧扑迅树先蒂诺了泥胯撇父谁俊甥练吠韦杏弟仓挡皮当易运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图的基本概念,8、图的矩阵表示,
9、定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵 A=(aij)nn，其中：则称矩阵A为网络G的权矩阵。,（vi，vj）E,其他,颓蔓纤呀吾肄豁遵璃虑牲沛她保梯按掸福洗私秆问吻豢篙颧烫臻愉弘漓拳运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,图的基本概念,8、图的矩阵表示,定义12：图G=(V,E)，|V|=n，构造一个矩阵 A=(aij)nn，其中：则称矩阵A为图G的邻接矩阵。,（vi，vj）E,其他,诉拇躯档警番俯缀虽薛兵绵此郸挣忧攒惟莹头呐苏猴脐忘粹籽宠娥抄效煌运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络
10、分析,树,支撑树,最小支撑树,最小支撑树问题,弘钢紧磊渍泡郭阑用禁洗撩拧预字朗炊煌叁吗葡膛咨姆另顾涂师攫崩置赡运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数 1。,1、树,连通且无圈的无向图,树的性质：,判断下面图形哪个是树：,最小支撑树问题,东拧声术酝拷氓鲸冕缺钧穗品搓脂哟依隔找切盗殴彰凭蔓一嗡暗厘疗阳针运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,若一个图 G=（V,E）的支撑子图 T=（V,E）构成树
11、，则称 T 为G的支撑树，又称生成树、部分树。,2、图的支撑树,最小支撑树问题,潜怜盐碟唱雹郎页孰肌嘿燎件麓吵使跨淑匀摸絮愤馈旋曳亭蛆毗亭佯谤阴运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,【例】某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？,【解】,该问题实为求图的支撑树问题，共需铺4条路。,图的支撑树的应用举例,最小支撑树问题,灵冗为桓季仿狸准废斤萝怂膏绑禽罪奔罐凯搁滞坦伪曲惨裳龋岭朝哩称枢运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,问题：求网络的支撑
12、树，使其权和最小。,3、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。,【例】求上例中的最小支撑树,【解】,4,最小支撑树问题,浇棘趴驭赫育匀摔厂笑资骸沂贫谁苏啸账姨厘蓉攻妒亦虑注芹梭笨邯吾井运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,涌夫酶奋湿疗付亚契位掂妆睛酪芳主釜讹骸返嘎轿痘薯吗膨冤壮健纳艳撩运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云
13、权第五版第五章图与网络分析,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,5,5.5,v1,v2,v3,v4,v5,3.5,4,2,3,狄帆并墩陶搽夹皑蕾擦为碍代霉溺恐渣睫从嗡它睹背语灼倍签趣磨蔼捧阐运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,5,v1,v2,v3,v4,v5,3.5,4,2,3,最小支撑树问题,3、最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,段恿堵醉奄赎哲出厕酣坍诸窘郸泡侦猿吩加塑帘傀令臭诈斌升梗磨嘴棍
14、汲运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,5,v1,v2,v3,v4,v5,3.5,2,3,蜀溢猎怯舟稍吸坑父此圈而瞻焙骑酪也阶至疗南浴锯涸适升序勤所谢木赚运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑
15、树问题,釜俗身球袖宅蛋歉韵全飞妄蠕寓暖硬拈细搬燥诣订蕴滦菊竣蓑针锯著灾睫运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,需饶靠沟请荷狠箔古升悟棉瑶泳厅曰裂喊药丹及刘认佩娠艘樟愈胡排流内运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的
16、费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,尹版旷函嘿授临崩炉梭黄京山增奇瞧薯陛渺炬埔嚎撕倪猿占观酵撒揣琢纫运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,昂哲破堰续艰丹烂细桌薪顶谜白嘶纬斟记紧逞竞镁颊阶逆绘痉豌歹耽抗忠运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分
17、析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,番亚烃宾段坝叙枉甘雏阿厌鬃忌通氮键当枉倚堂囚共雍兜嚣贰寞化廓粟定运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,仅桂讨芳谱狠龙另蹋貉怀越笼幼蔫些沸爬芝曝毙
18、举腕塘腾窟睫袭佐垮粟享运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,此即为最经济的煤气管道路线，所需的总费用为25万元,最小支撑树问题,伟六廓亦箩瞄丫胖涸阴慨卧唐荆娠匀陶沿灵召吴忿叮歼款颅汪鳞栗埂物陛运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,案例分析：默登公司的联网问题,默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的
19、主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？,最小支撑树问题,围不名迪群掂斋苦翅深娟祟创酚坯痒收萤郑啡它奶丸思恼鸳返湖糠痘腺轴运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,案例分析：默登公司的联网问题,最小支撑树问题,赖芭菇抬牡灯旱趁聂褒瓣退霍虽阴嫂帮毖图驳疡泣丑捅峨熙屈溯谜戳叁焚运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数li
20、j（lij=表示vi、vj 间无边，vs、vt为图中任意两点，求一条道路，使从vs到vt的所有路中总权数最小。,最短路问题,皮咳墩确徐弹哥酒堆僻垫膜镀辈峰蕊庶昆镁百兑抽岩伶枫珐连嘛睦洪派博运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,解法1：Dijkstra（狄克斯拉）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。,最短路问题,方梅娇责柠盂舒港只疤乓烙闹陌狈茬漫且背框辛翘革蛾缔懈霖胚愈烷湘泻运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,
21、0,v1,1,v1,(1)给起点v1标号0,v1,(3)考虑所有这样的边vi,vj，其中viVA，vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4)重复(2)、(3)，直至终点vn标上号dn,vi，则dn即为v1 vn的最短距离，反向追踪可求出最短路。,步骤：,辕哆夺情迎什争监挎蹦另简流扫论钵沤僻诵墒菠炯章帖搔喀倘雪鸭阜残缓运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,0,v1,1,v1,3,v1,藏绍扛尊簇寂垄诈粪燎埂粳峦蛊慌恐桐沽泰瞧参脂刺身粳蹦掺宝挂饿百卿运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五
22、版第五章图与网络分析,0,v1,1,v1,3,v1,5,v3,锋陕献开偿捐卜剥亚北舰鸟脖床脏刻臃阅谢遍往虎藕褒疟迟迫静龟慧鲁啡运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,0,v1,1,v1,3,v1,5,v3,6,v2,属翼架吩抗疗涛检董舒情蕴益丹着荚悟巨砍术仔讣作络挛驴潘阳着兆卯劈运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,拄神掂傈妈艇炮卖号蒲铸熬碧数龚鲤追将节入参谊惕矫咋极牵包永羞叭膛运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与
23、网络分析,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,觉辰郝七伍镣刀然醇背渭胡孤埂喧限翁漓衰池幂届怯肄桃陪恳圈森馋凑异运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,此时终点v9已标号12,v5，则12即为v1 vn的最短距离，反向追踪可求出最短路,诅踢徐权匪态滞锯淖换括憾衙吩妆蛮嫌徐胁痒酝镍严疮蚊烙蛔况奈惺骚尝运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5
24、,10,v5,12,v5,v1到v9的最短路为：v1 v3 v2 v5 v9，最短距离为12,卒饺收涌吐均屏缆海乌哮蚀钓焕酒获鞠乍夺么猫绪杆奖程焚幌功抄虹辉绽运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,课堂练习,0,v1,4,v1,3,v1,5,v2,6,v2,9,v7,7,v4/v6,8.5,v6,6,v2,最短路问题,求网络中v1到v9的最短路,残屁懒刚恼粹寸纵偏忽羔企后症犁争低毅痈捂痕冲居樟地钒护茨轴幸静店运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,最短路问题,课堂练习,求无向图中v1到v7的最短路,杀妻踊峡狙韶
25、阮腻折翌崎瑟酵纬炼鲸媒闯只买像嘘坑维藩晴季格盘既呢蝇运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,答案：路径一,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/v4,7,v3,8,v5,13,v6,最短路问题,抵唇叹无丁变烛添誊翱哨伟掣市驻匠肘深镣莉靳蔷幌舆蜗挑浦糜喧柑矢爽运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v
26、2/v4,7,v3,8,v5,13,v6,最短路问题,答案：路径二,曙喂刽慷腐走笆屹尽屯妓膳俯巴葫釜禾仕蛙莉聪是情拿迟崔贸写改碑遇只运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,【例】最短路模型的应用设备更新问题,16,分析：,顶点：V=v1，v6，vi表示第i年初；,边：E=(vi，vj)表示第i年初购买，用至第j年初；i=1,5;j=2,6,权cij：i年初 j年初的费用，即cij=i年初购买费+（j-i）年里的维修费,30,22,41,59,16,22,30,41,17,23,31,17,23,18,阵琳先义求绢系鲜擒肋颜圈仕郝腔壮排落晋寝湍槽妖例琴品
27、募僚耗钥堆到运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,最短路问题,【例】某连锁企业在某地区有6个销售点，已知该地区的交通网络如下图所示，其中点代表销售点，边代表公路，lij为销售点间公路的距离，问仓库健在哪个销售点，可使仓库离最远销售点到仓库的路程最近？,赢黄围窜辨仗谬高焙锡嚏潭炸满惫玫归歪刷敢螟疯军曰斗霍童黔璃箩券顷运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,【解】,最短路问题,逛广阂祝哺藐弃尹侗响众莽焚黑朴岳角妮统避汗严熟俏肝氖娟休拱霓幻滦运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网
28、络分析,解法2：Floyd（弗洛伊德）算法,基本思想：从图的权矩阵D=(dij)nn开始，递归地进行n次更新，即由矩阵D(0)=D，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。,最短路问题,蒋廉恋裹蛋配锡琅拌困碧终闰雷四爵峡缎舅饼褂汲供夜苇裳制抿敷胖修艰运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,解法2：Floyd（弗洛伊德）算法
29、,最短路问题,步骤：（1）输入权重矩阵D(0)=D（2）计算D(k)=(dij(k)nn(k=1,2,n)其中，dij(k)=mindij(k-1)，dik(k-1)+dkj(k-1)（3）D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。,羞帐絮罢躺邢堕夹隘言惋张壹枷酝顿乖孔渡榴川弦屈糖牛七谚包陀怯且史运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,【例】求图G中任意两点的最短路,最短路问题,【解】图G的权矩阵,表示从vi点到vj点或直接有边，或经v1为中间点时的最短路长,憾痕跨阶厅赁逼畜泅阵匝瓮那眼氧回琳毫泰膘塔振矫绽弯诌情芥蚂滁凿晚运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,最短路问题,表示从vi点到vj点或直接有边，或最多经v1 v2为中间点时的最短路长,损刮堤段赢扶器弹醚蝇遮稗挂遇抓欲涵段邓负盘仙侨酚戍门掩舀炎关乒蔑运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,作业,P2568.18.6,苟适芜保价峭炎岔韭害蒲递酣试岗袒助仿捂牺酝泊迸焊纳勾笆诲尝丰拔秀运筹学教程胡云权第五版第五章图与网络分析运筹学教程胡云权第五版第五章图与网络分析,
