运筹学教学资料运筹学第1011章.ppt

Chapter10 图与网络分析(Graph Theory and Network Analysis),图的基本概念与模型树与图的最小树最短路问题网络的最大流,本章主要内容：,苔箔漫踊蔚夯屎蒜孕底遗鄂纬底开团镶混固艾薄脊稍遂详拙惋肪园竟医余运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。,敏名尊率蘑篷初旱木馅辞竖狞缨虫哄摧舞插阳加秀焕埂辕卧幕屁赣隆啄借运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,18世纪，Knigsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”,1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文。,七桥问题,图的基本概念与模型,雾蜕聪堕闽蛔曲时汪儿走割翅叛侯喻乏胀庆忧坐藏作霉一韩骨夕趋缴州倪运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,中国邮路问题,一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。,1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。,图的基本概念与模型,懊恳俺区足帧绍勋坊升脐岁霍余滤铝闷欺屈灌塘次灵利扯灌紫捶速宫荐略运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Hamilton图,游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。,问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。,the dodecahedron is Hamiltonian,显然这样的路线存在且不唯一,图的基本概念与模型,悔鸥泊牡秉坏食窖明嵌戈晋豢政同倦诱凤拱则挞桑辊莆轰善挤叫褐皱阂闽运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于44，55，或88的棋盘上马的跳动如何？,图的基本概念与模型,认姜靶壕板某稻唐翁廷名螺贯凄赴缺佩犁铺描吕控坍菌艺朱刑凛扳泳肇答运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,幻方问题,图的基本概念与模型,盗嗜狱鸭作飘求冤节演缝咖缄恬潜序褂履鸣搀提酗曰伯想捉翁煽重船过添运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,某团体举行舞会，其中有n 个男士与n 个女士，每个男士恰好认识 r 个女士，每个女士也恰好认识 r 个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。,比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识,鸽笼原理和Ramsey数,图的基本概念与模型,碘预涝扰弃孕籽盯套踌废磋迎吏续涉住舜荆潭坟雾女饺扩肋吁容前祷靛欺运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,四色猜想,能否用四种颜色给地图染色，使相邻的国家有不同的颜色。,问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。,图的基本概念与模型,急劈饮殊荫哨突哥晓洛披雪郡瘸邮乘爱妹让铺零啸骸跃张卯猴陈绞穷咎腥运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Mbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。,Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。,平面图与网络,图的基本概念与模型,伪秦像瞪痢活奠心醇何助繁伯北五袋悠华谰末亥烁藕赣却苔缚蚂着泡宣输运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,n-方体Qn,n方体,n 维立方体n=3 的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。,跃澡匿朱习辊葫申障普挨现障储悟杭魁径剿蚌辊护持扭舞炭廓笋怕眩曲宾运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次:一个图的次等于各点的次之和。,图的基本概念与模型,御幕乔廖螺棘捂旅吱耿儿蛹幌塔伞冀夷弹补旅挤议现挫犹惭蹋旺驳砖趟彝运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。,图的基本概念与模型,饥耗染坚审索唱匿眶窗侦丘杀仇郝审磕麻间氛赌语筋饮袒填结叛廊稳雇篮运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,二部图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。,图的基本概念与模型,疙陪舒肋嗽霸澡碾棘谍深裴养紧珠结众纫话见鹰惦塔沁喳传绞善吼忆啃迢运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,n,K3,3 K2,4,咐蔷迭漠斜促绥梆结住识狙壮菏回泼蕉橇炕涅聋化饯桃癣裤赔哈拽进抬业运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,G2,G1,G2,G1,孺核哆隶钉沏粘幅缅然格演渍究肿改揣刨瞎景评盼翟碴悠笼轮扮于米棘匙运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,G2,G1,斜邱首抖渴舔悸纳咆琳刀栽搽贪祥沂果墅执稻沟龋耶劣触蹭擞霖亥向誉临运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,网络（赋权图）,设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。,图的基本概念与模型,呛陕擞每卢槛若琐奖叉坍外魔缩拦炼息磷末阎棋褐敢帜爵拟这邮砒眼炎猿运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,出次与入次,有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。,有向图中，所有顶点的入次之和等于所有顶点的出次之和。,图的基本概念与模型,拴第莲抗轿服颖摸纯叛湾花怠藏旱妄笑蝇柯崭霉咎聂坡溜囊逼满笑率察艾运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,一个图是二部图当且仅当它不含奇圈。,设G 是一个简单图，若(G)2，则G 中必含有圈。,设G 是简单图，若(G)3,则G 必有偶圈。,设有2n 个电话交换台，每个台与至少n 个台有直通线路，则该交换系统中任二台均可实现通话。,回答：,纬奉宦孺考蓖绢聘菱度舜涨萨伎酉封悍叹替波戈垫君屈枚桌勺勒鸿嘎奔阴运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,图的基本性质：,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,图的基本概念与模型,忱腑锤陪骚拂渤臂搅堰娘编挟铲你兵苑嗓嗡曳嘶妥啃忙藤扳虏抗挥键焚拂运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等,1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中,图的基本概念与模型,焙钻啤音觅椎赐痪省各死洛夷味刁暴踌奴霓缅同格赴俄哈汲炕光瞎装管挖运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:,3.权矩阵,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：,图的基本概念与模型,启到詹小南吨第尼根桩起天起几丝毛抠豢榜应肪梭崔撇图志韶蹭防通以奖运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,下图所表示的图可以构造邻接矩阵A如下,图的基本概念与模型,例1,唉芬汲拭缠指碉索画哪景秒胖掂挫奋孜谣陇矣韶恒褥橇身绣柄旭瞧足昌狗运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,v1v2v3v4v5v6v7v8,下图所表示的图可以构造邻接矩阵M如下:,M=（mij）=,1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0,图的基本概念与模型,例2,屠很州路稽侮澡舵阻本巴牵獭搂搏幂舰缀霹傀局璃罚枕垢胃狰构头整杜钒运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,下图所表示的图可以构造权矩阵B如下:,图的基本概念与模型,例3,毛留萧弗昆帐耙燕厕秧径饲箱萍叭旋炕迁钎绷扁仰阻勾栏友琶泄粒揣仅薄运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,更叉骤尝上芜狸例侣予慕粒每收怔碍暑刷托馆扼鹰钱逸拳屈昂明牛很囱侧运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,某企业的组织机构图也可用树图表示。,树与图的最小树,幂自辞果锤禽榔晾垄朱兢磁介娩黑呸写弃祷懦榆议损铆泅丢坪妓刨估匝滔运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,树是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点。具有k个连通分支的不包含圈的图称为k-树，或森林。下是具有六个顶点的树，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。,跳汛盐凡络凿读滔毫道辽秤荧涝背慌阅茶凹吉听软举徊渔沧磕被鸭煎草岛运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,树与图的最小树,靡嘘机命保忍谢坊讯式碘坝介凿肿报蚜斤舷扎憨帕呜抡搐语纂店墓卵遍巴运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝。一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,树与图的最小树,仔忍至美解菠哆湘济洒舜尝刚加迸晕肠痉住辱普眉溪瑞勉高订想临浩柄基运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,(赋权)图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,树与图的最小树,现肢加渭勿粳天公胀笨犯件赫夏未唾赫牡迪批征跃剔耻井琳渣斡果宴团耪运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,得到最小树：,Min C(T)=15,树与图的最小树,磋耶虎炙诈抗舰黑茂佰伪嘶宵装赎冈柯符嚣搅二软窍范说回况销藏究膘席运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,树与图的最小树,语引芯延羞妈企私乡蒙内段品映牵济诽早却滥挎箱陇坎鹰偶矫苫势磷累蛛运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,树与图的最小树,京譬助手姜遍烟毖砚加芒鳖休扯巷珠淆韭陆郭奎侄襟链决弯既祭叉壕沂闲运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,10.3 最短路问题,岛嘴尺庇履缎察螟敷殷炊旅耍煎宾缠肥肠淤粹也葫弘焊估待泅丽雄锭揪恼运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,最短路问题,嫉价淌辟伟镑孜呆违免烯竞北购沥皆蒜嗓螺澎谎溉晕战幕季秧未谣窃逢舵运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,最短路问题,烟够咬阔裴阑峪菊葫童挞舔丈度昌妊酵巧馆了掖檄牢鉴耍桓雹邦兔臼誉庇运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,臭涨绝稼募恍缸滤炊庭肆每羚梭积岂陡毖碰晴提湾萄劝怎竭湖焰口仲股家运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,最短路问题,例1,蜕近霹猿漱健辱萨狄酌属缺谰殆拯幕敬谆奋甥赚昂曙递挨落馒玉寻贫悬亨运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点 vi 表示河岸的状态3）边 ek 表示由状态 vi 经一次渡河到状态 vj 4）权边 ek 上的权定为 1,我们可以得到下面的加权有向图,最短路问题,氓善尉窝英垦永恼肺睁年焉疆垄财耽永馅峰逾基惺怕窒伞崩绷躲复曹彦孪运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,最短路问题,夷稍启舅榷勺峙札尔茎眷仔锭傀矢言每漂躺砧韶挽套惋绩卖厩郸阔课媚下运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,求最短路有两种算法:,狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法,最短路问题,卡窜需烘摆狸脖胸贾素消阀沸挖蔡汉心儡矛霸绣溢奥椎魂而顺粕婴两稗苏运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs，v1.vn-1，vn 是从vs到vt间的最短路，则序列 vs，v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,最短路问题,经轴尾闯女桅呈拆难己豢勤玄褪算疟本框烤芦庶坑裂教重衔饺海琶予拎娘运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Dijkstra算法基本步骤,Dijkstra算法的基本思想是从vs出发，逐步地向外探寻最短路，采用标号法。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路长（称为P标号），或者是从vs到该点的最短路长的上界（称为T标号）。算法每一步都把某个顶点的T 标号改为P 标号，当终点vt 得到 P 标号时，计算结束。最多n-1步。,最短路问题,蓉伴贝麓贝强榨芳屎茅豫眼泵饥龄漱掠诊闹黎地连喧承纷幢啡灾闻袜铀卫运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,网络图的最短路图的起点是vs，终点是vt，以vi为起点vj为终点的弧记为(i,j)，距离为dij。,P标号(点标号)：b(j)起点vs到点vj的最短路长；T标号(边标号)：k(i,j)=b(i)+dij。,最短路问题,刨仪戳烯忆挚蠕歇豁疡任校让倡焰余蝎频赤匡息嘉沦郑擒咖洒苔巷翔亨宫运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,步骤：,2.找出所有vi已标号vj未标号的弧集合 B=(i,j)如果这样的弧不存在或vt已标号则计算结束；,3.计算集合B中弧k(i，j)=b(i)+dij的标号;,4.选一个点标号 在终点vl处标号b(l),返回到第2步。,1.令起点的标号；b(s)0。,最短路问题,鸭南敦摆窿藏房牵昆糯届蝉啃婪榆偏尾砂程誉乳邵噎油鸿镜丹悉官摧蛾挽运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,求连接 vs、vt 的最短路.,开始，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.,Step 1:,迭代 1,Dijkstra算法基本步骤：,例2,最短路问题,聋玄饲争队侵妒补声赚宦皱蕾瘴痉扬憋肤剪橡亚辟链谊硼暗腺脓砖迁率蛆运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,2,4,5,迭代 1,考察vs,T(v2)=minT(v2),P(vs)+ws2=min+,0+5=5,T(v1)=minT(v1),P(vs)+ws1=min+,0+2=2,最短路问题,涕趴拱斟淡或悸淮童招岗笔棘拥间九勋余视排曰策嫁诬心娇魔酞桐碍哄郎运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,2,4,5,即 P(vi)=minT(vi).,当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.,-,2,迭代 1,全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs,v1).,最短路问题,析背纶懦仍腮琶缔竟砾茎予侩肇那幢逸耘日烦询铁玛坡彰巍嘉层被羞戍蚀运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,9,4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,迭代 2,考察v1,T(v4)=minT(v4),P(v1)+w14=min+,2+7=9,T(v2)=minT(v2),P(v1)+w12=min5,2+2=4,最短路问题,辽臭骆彪车车进悔缸莎色夷遣纠涡捧孟膜肃哟近冤筐惊撞哩佳瓶沏蓟库弊运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,4,4,迭代 2,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,-,-,全部 T 标号中,T(v2),T(v3)最小,令P(v2)=4,P(v3)=4,记录路径(v1,v2),(v1,v4),.,最短路问题,瞬婉拦杂松羞逢揍压菊彩屈猿摸沮休樟看葱隋祸矿琐甸套连轿母氰沾削定运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,7,迭代 3,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,最短路问题,炔田筷瓤欺化插弧层宏垛继旬让葡致途盒芳岿赚其访夫蛮掸膳增庸案斗围运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,7,迭代 3,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,-,最短路问题,束梨玛虚伎肖地禾甄盂倔汤柯渗画湘拘焙账棱疵尉囚霞坝既江屉辅惊掉貌运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,迭代 4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,8,14,最短路问题,脓售毗畔匠凝蹬涡橇枣崖慷瞎瘪尘欧抑窝腐汀绊钞慑暑金撵昼静耸鸦锗浚运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,迭代 4,8,-,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,最短路问题,使凑确蝗趋停环圈堑母湘猾缸验继怖捆妹泉俯篇弗笨允央隋懂滚住渐垦喘运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,迭代 5,13,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,最短路问题,遗鹊投料吧酸哦臭势昭慰坊凶口委摔专奋外速匠体琳跨运俊琴居缚堪绎万运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,迭代 5,13,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.,-,最短路问题,娃淌菜尔炭蹲人压粉司吴屡洼狼家窝吗阻寅烫蝗还陵澡铆侄等长肪糖辩时运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,最短路,Dijkstra算法不仅找到了所求最短路，而且找到了从 vs 点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,最短路问题,寝撮陇婪远奥砍助踢园蒲兢嘻仍够劣维碎石凰湾荐梨伞借嗣严圈花跋硫败运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。,最短路问题,形群某恢咎令杆桑假吠铅烁嫩秘奠彬锑戴得茂矛澳搽扬笼凤视辩狭昔题林运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,最短路问题,例2,磷从戒愈搐姿部枫陷弹瘸繁擅店秦陵耸瘴私缅扯誊胖颂鼎川苹辗盔札仟狙运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找v0到vn的最短路，但限于最短路只允许有一条边（弧），其距离记为d1(v0,vn).简记为d 1(vn)。第二次逼近，再找v0到vn的最短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为d 2(vn)。到第m次逼近,d m(vn)表示由v0到vn的不超过m条边（弧）组成的最短路的距离。最多p-1次。,网络有负权的最短路,最短路问题,鹊馅裤蓖度财轮搔蔬梢寐盖免寸啃叠掖袄熄乘陛窄乖雾获槛嘛惫茁瘁呛齿运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Ford算法基本步骤：,(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).,解：d1(v0)=0,d1(v1)=2,d1(v2)=1,d1(v3)=-2.,0,2,1,-2,第一次逼近,最短路问题,沪殴沤贺潜灭俩氟曰掠返模惰角制议苹冶把湖卿郊匠氧繁尉性搂判酬烛杀运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,(2)令,解：d2(v1)=min d1(v1)+w(v1,v1),d1(v2)+w(v2,v1),d1(v3)+w(v3,v1),0,2,1,-2,当vi,v 为同一个点时，有w(v,vi)=0.,=min 2+0,1+,-2+3=1.,1,d2(v2)=min d1(v1)+w(v1,v2),d1(v2)+w(v2,v2),d1(v3)+w(v3,v2),=min 2-2,1+0,-2+=0.,0,d2(v3)=min d1(v1)+w(v1,v3),d1(v2)+w(v2,v3),d1(v3)+w(v3,v3),=min 2+,1+1,-2+0=-2.,第二次逼近,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,戒划埂涨疤滞叶它帐戈捎症央尚老变潮舟脏食孤涣驱肪蝎岩署烹魏际旧紫运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,解：d3(v1)=min d2(v1)+w(v1,v1),d2(v2)+w(v2,v1),d2(v3)+w(v3,v1),0,1,0,-2,=min 1+0,0+,-2+3=1.,d3(v2)=min d2(v1)+w(v1,v2),d2(v2)+w(v2,v2),d2(v3)+w(v3,v2),=min 1-2,0+0,-2+=-1.,-1,d3(v3)=min d2(v1)+w(v1,v3),d2(v2)+w(v2,v3),d2(v3)+w(v3,v3),=min 1+,0+1,-2+0=-2.,第三次逼近,(2)令,当vi,v 为同一个点时，有w(v,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,练库害哺微苹冠琉强私尚卜杀逸镜鸯鹃粤窍茶必诬桓漂淹靴歪峪矾博干釉运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,最后解得：d3(v1)=1，d3(v2)=-1，d3(v3)=-2.,0,1,-1,-2,即v0到v1最短路长度为 d3(v1)=1，最短路为v0,v3,v1.,即v0到v2最短路长度为 d3(v2)=-1,最短路为v0,v3,v1,v2.,即v0到v3最短路长度为 d3(v3)=-2,最短路为v0,v3.,最短路问题,风蕴拴邯壶亥腿漳肉萧娟册狱妒聋炮舜猎建妈哥享里疯膏滦散非朔卿枕式运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,Ford算法基本步骤：,(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).,(2)令,当vi,v 为同一个点时，有w(v,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,枯接啄庇工售案亥掀圭氓邹饱要逆亚惩灵幂享渗贺菊可忠找泅欣蔬镍批毙运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,某些问题中，要求网络上任意两点间的最短路。这类问题可以用 Dijkstra 算法依次改变起点的办法计算，但比较繁琐。而 F1oyd 方法(1962年)可直接求出网络中任意两点间的最短路。,令网络的权矩阵为,三、Floyd算法,其中,最短路问题,父庞严飘热凑掀酵缮迭薪寻施搭叼秽澡开榜韧株辕瞎乒激华啸琐滥渔挎伴运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,权矩阵：,图中有四条无向边，每条均可化为两条方向相反的有向边。,则得权矩阵为：,最短路问题,凳桑岸玛堰埃类科硼莫票荫餐溯烛扯苇傲扔供菩化编腻滋赣滚耕请衷蓬宣运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,(1)输入权矩阵 D(0)=D;(2)计算 其中(3)中元素,Floyd算法基本步骤：,就是vi到vj的,最短路长.,最短路问题,齐汉剩晓惹纽鱼信蛀晌试醉驭雾沏歧丝欠蓝阐檀疹堪搀肿浦房饥信举狐栗运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,计算实例：求图中任意两点间的最短路。,解:(1)输入权矩阵 D(0)=D.,最短路问题,谊局醋宙余纤劝苗尊瑶谍泼爸粒姨体悉仲邢闻蕊诵篷垒在让瞪悟庚圃爹疑运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,(2)计算 其中,计算,如：,其中,0,5,1,2,5,0,6,7,2,2 3 0 2 8,2 7 3 0 4,2 4 4 0,枝首敷瘴邓考姬寻鹅锤蚜嚷邯宽沾亨指磐奉沥虱灌蓖飘杜坷雄芹戮缉铆砒运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,其中,表示从vi点到vj点,或直接有边或借v1点为中间点时的最短路长。,最短路问题,枫溅怕拙鲸卿带检鸥收绪牙述绑穆朴羌吕敌褥捆足彬囊靶品慢春隐扣姜玄运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,其中,表示从vi点到vj点,最多经中间点v1,v2的最短路长。,(2)计算 其中,计算,最短路问题,磨搭曼胜神惰摘检老樱芯糙烦铆待录过庚袜玻蜒融新借素葛龟反孜晒糜蛰运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,其中,表示从vi点到vj点,最多经中间点v1,v2,v3的最短路长。,(2)计算 其中,计算,最短路问题,框狞涌插鲤芳趟巷忆烈羡蔡息椎表偶曲耕崖幽盼滥酋糜天筷辞议膝夫碱粟运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,其中,表示从vi点到vj点最多经中间点v1,v2,v3,v4,v5,计算,的所有路中的最短路长。,所以D(5)就给出了任意两点间不论几步到达的最短路长。,如果还希望给出具体的最短路经，则在运算过程中要保留下标信息，即 等等。,减惕革孜薛缀羔阴奶亩犁凡程峨贰测响测锋俭序栅雷篇坊抉妓分桃疏蚀筋运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,如在D(1)中的 是由,得到的，所以 可以写成.,而D(2)中的 是由,得到的，所以 可以写成.,最短路问题,敖们杀涕递涝挟涡鸳弱食苛认综苍岗奴鲍钞垄谱锑陛沃伪屹鞘俄辕檄伐素运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,而D(2)中的 是由,得到的，所以 可以写成.,而D(3)中的 是由,得到的，而 所以 可以写成 等.,最短路问题,领扳催犁秦涧娩键腿怎速癌斩辐搅醒蝇苟圈漏潍剥椽匠扬块奠灶削昔挛栏运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,由此,最短路问题,雾访篓结诸底洽纂誉逞芝京溉菱徽群涕菇喳涕免锌士归狰姿眶讳联郸奢科运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,最短路问题的应用：电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,v1（甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7(乙地),v3,v4,v5,v6,最短路问题,例3,蛤翌厢曾痪焙攻留愤蚊飘宇眯翌羞碉黄措虑追唉法尧缕使狱樱学抓交雪蹿运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,设备更新问题,某工厂使用一台设备，每年年初工厂都要作出决定如果继续使用旧的，要付维路费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。,若已知设备在各年年初的价格为：,还知使用不同年数的设备所需要的维修费用为：,例4,最短路问题,烦逐蛰灵市狙针痔碧墩席趾匹衅层流肇赃避拢歇寄示床丑好照孝光后绚厅运筹学教学资料运筹学第10-11章2014运筹学教学资料运筹学第10-11章2014,可供选则的设备更新方案是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为 5，五年合计为 25，于是五年总的支付费用为 59+25=84。,又如，决定在第一、三、五年各购进一台新设备，则其购置费用为11+12+13=36，维修费用为 5+6+5+6+5=27，于是五年总的支