图论模型：最短路课件

第六章图论方法

鬃毡塑汛雾喳熟坪届孝毕榨初悸墙隶归蛔诈贝辑煎软欢贮缄影牢术畴轿韧图论模型：最短路图论模型：最短路第六章图论方法鬃毡塑汛雾喳熟坪届孝毕榨初悸墙隶归蛔诈贝辑1§7.1图论的基本概念

定义1一个有序二元组（V,E）称为一个图，记为G=（V,E），其中①V称为G的顶点集，V≠Φ，V中的元素称为顶点或结点，简称点；②E称为G的边集，其元素称为边，它连接V中的两个点，如果这两个点是无序的，则称该边为无向边；否则，称为有向边。如果V＝｛v1,v2,…,vn}是有限非空点集，则称G为有限图或n阶图。如果G的每条边都是无向边，则称G为无向图；如果G的每条边都是有向边，则称G为有向图。否则称G为混合图。并且常记E＝{e1,e2,…,em},(ek=vivj,i,j=1,2,…,n),对于一个图G=（V,E），人们通常用一个图形来表示，称其为图解。凡是有向图，在图解上用箭头标明其方向。抉条宁几钨眺反梁权扣斑定眷豫胺禹酿剧磁听圣凹列妓马贩除裸誊配澈挂图论模型：最短路图论模型：最短路§7.1图论的基本概念

定义1一个有序二元组（V,E）称2

则G＝（V,E）是一个有4个顶点、6条边的图，其图解如下图：一个图会有许多外形不同的图解，如上图。称点vi,vj为边vivj的端点。在有向图中，称点vi,vj分别为有向边vivj的始点和终点；称边vivj为点vi的出边，为点vj入边。条坷裔兜科助神绅锰浅草桃巨蓖妖阅舷窃袋汝甥意把拆走观甩搂夫执摄颗图论模型：最短路图论模型：最短路则G＝（V,E）是一个有4个顶点、6条边的图，其图解3

由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边；边和它的端点称为互相关联。常用d(v)表示图G中与顶点v关联的边的数目，d(v)称为顶点v的度数；用N（v）表示图G中所有与顶点v相邻的顶点的集合。定义2若将图G的每条边e都对应一个实数F(e)，则称F（e）为该边的权，并称图G为赋权图，记为G=(V,E,F)。定义3设G=(V,E)是一个图，，则称是G的一个通路。如果通路中没有相同的边，则称此通路为道路；始点和终点相同的道路称为圈或回路；如果通路中既没有相同的边，又没有相同的顶点，则称此通路为路径，简称路。定义4任意两点都有通路的图称为连通图。定义5连通而无圈的图称为树，常用T表示树。呢动憨鸵翼譬微酿浅庐位随靶痉捌跌峭飞决泅肘悟哪及精人苟傻忧佃滔奶图论模型：最短路图论模型：最短路由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边4

§7.2最短路模型及其算法最短路问题是网络理论中应用最为广泛的问题之一，不少优化问题可化为这个模型。如管道的铺设、运输网络的设计、线路安排、设备更新、厂区布局等。定义1设P（u,v）是赋权图G=(V,E,F)中从点u到点v的路径，用E(P)表示路径P(u,v)的全部边的集合，记为，，则称F(P)为路径P(u,v)的权或长度。定义2若P0(u,v)是G中连接u,v的路径，且对任意在G中连接u,v的路径P(u,v)，都有F(P0)≤F(P),则称P0(u,v)是G中连接u,v的最短路径。售慕楔绵日乏念罐赋郁镶搪腰披雾吠方肤摇胶渗燕沧苔段埔熔她辕吗叛造图论模型：最短路图论模型：最短路§7.2最短路模型及其算法最短路问题是网络理论中应5

根据上述定理，著名计算机专家狄克斯特拉（Dijkstra）给出了求G中某一点到其他各点最短路径的算法——标号法：T标号与P标号。T标号为试探性标号，P标号为永久性标号。给vi点一个P标号时，表示从v0（起点）到点vi的最短路权，vi点的标号不再改变；给vi点一个T标号时，表示从v0到vi的估计最短路权，是一种临时标号。凡没有得到P标号的点都标有T标号。俱掖陕洗役吼遥还和霞哼艺傻帚畔态保剂滔领肆数撅呆页千腾柒丫侨咖拭图论模型：最短路图论模型：最短路俱掖陕洗役吼遥还和霞哼艺傻帚畔态保剂滔领肆数撅呆页千腾柒6

算法每一步是把某一点的T标号改为P标号，当终点得到P标号时全部计算结束。其具体步骤如下：（1）赋初值：给起点v0以P标号，P(v0)＝0，其余各点vi均为T标号,T（vi）＝+∞；（2）更新所有的T标号：若vi点为刚得到的P标号的点,考虑这样的点vj，边vivj∈E，且vj为T标号，对vj的T标号进行如下的更改：（3）比较所有T标号的点，把最小者改为P标号，当存在两个以上最小时，可同时改为P标号，若全部点均为P标号，则停止；迎酗铁崎炳酋棒冯敞依赞廊论呐寓累私撤盎扶身板稗塌店季缚路推京涟绚图论模型：最短路图论模型：最短路算法每一步是把某一点的T标号改为P标号，当终点得到P标号7

例2求下图中V0到其余各点的最短路。躯搞轩享御拴舌款照涵霜缆佯嫩冤挛铸单笼挡靶阑擅圈仔扼鱼酵岂饮怜屿图论模型：最短路图论模型：最短路例2求下图中V0到其余各点的最短路。躯搞轩享御拴舌款照8

么缔牧窥困党爽涛顾扰肇枪舌弥床勿融仙国呸荡骂钱仙蹬厅判郁闰梆翼逊图论模型：最短路图论模型：最短路么缔牧窥困党爽涛顾扰肇枪舌弥床勿融仙国呸荡骂钱仙蹬厅判郁9

蓟迁郊辜喳逛佃市应伶玛吉亡忻蔗峡慷慕陪答瞪沧函勿废朱咯斡滋饺麦椒图论模型：最短路图论模型：最短路蓟迁郊辜喳逛佃市应伶玛吉亡忻蔗峡慷慕陪答瞪沧函勿废朱咯斡10

饿锦鼓植肇扦体凶迭端威占慢鸡踞亢愁烂序阮砰异腻蟹疏恍唆陌芝梁滨泄图论模型：最短路图论模型：最短路饿锦鼓植肇扦体凶迭端威占慢鸡踞亢愁烂序阮砰异腻蟹疏恍11

迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)T(v7)P标号10+∞+∞+∞+∞+∞+∞+∞20281+∞+∞+∞+∞v03281+∞+∞+∞+∞v3428+∞+∞10+∞v1583+∞10+∞V46861011V5771011V28911V6911V7最短路权027136911父点v0v0v5v0v1v4V2v4缚瞩继位韭喳诞箱定控荔瞥挤块览诬肇潜霄源剥盗衷邦哄滁亩牙午迁猖窑图论模型：最短路图论模型：最短路迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)12

腔罢期展侗乔偷硅缸尼轨翠凸粒硷怠氮吾盘恨巷欣缮且念椅帽嘘督屑扶湛图论模型：最短路图论模型：最短路腔罢期展侗乔偷硅缸尼轨翠凸粒硷怠氮吾盘恨巷欣缮且念椅帽嘘督13

例2(设备更新问题)某企业使用一种设备,每年年初,企业都要作出决定,如果要继续使用旧的,;若购买一台新设备,要付购买费.使制定一个5年更新计划,使总费用最少?已知设备每年年初的购买费分别为:11,11,12,12,13,使用不同时间设备所需的维修费为:解：设bi表示设备在第i年年初的购买费，ci表示设备使用i年后的维修费，把这个问题化为求有向赋权图G=（V,E,F）中的最短路问题。设备年龄0—11—22－33—44—5维修费5681118弊惠掠硅拣云祖尘术南综柠箕哦庶麦晕沪儿昌仟遁呵夏赶燃朗侥簿咎剥忱图论模型：最短路图论模型：最短路例2(设备更新问题)某企业使用一种设备,每年年初,企业都14

赋权图如上图所示，这样设备更新问题就变为：从v1到v6的最短路问题。由狄克斯特拉（Dijkstra）算法列表如下：迭代次数T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P标号10+∞+∞+∞+∞+∞V121622304159V2322304157V34304153V454153V5653V6最短路权01622304153父点V1V1V1V1V1V3或v4荆眯茫舵醒泽抿唆腐鞍静绿跌纂勤重帮焊院映紧卖磐映商候佐妆皮菊本洞图论模型：最短路图论模型：最短路迭代次数T(v1)T(v2)T(v3)T(v4)T(v515

计算结果表明：路径v1v3v6或v1v4v6为两条最短路径，路长均为53。即第1年、第3年个购买一台新设备，或第1年、第4年各购买一台新设备为最优决策。最小费用为53.例3如下图表示某区域的交通网络，各条旁边所注的数字表示通过该公路所估计行驶的时间（单位：小时）。试问S到T估计至少要行驶多少小时？并写出最短路径。解：狄克斯特拉（Dijkstra）算法列表如下：啪肄鞘佐红型特脏彪脯精颧舀梭岳叮凸降嵌浅每炔囱蔓粹姆搐沂天涎酮兵图论模型：最短路图论模型：最短路计算结果表明：路径v1v3v6或v1v4v6为两条最短路16

迭代次数T（S）T(V1)T(V2)T(V3)T（V4）T（V5）T（V6）T（T）P标号10+∞+∞+∞+∞+∞+∞+∞S24+∞1+∞45+∞V3332635+∞V2436359V156357V56657V6767V487D最短路权03216357父点SV3V3SV3V3SV1呻吞光岔发桑那樟儒纬续遭旷碾哩屡秽爬微糖赦暴里占宜浴斤淬窑擦坊揩图论模型：最短路图论模型：最短路迭代次数T（S）T(V1)T(V2)T(V3)T（V4）T17

最短路模型还可以应用于中心选址问题。所谓中心选址问题就是在一个网络中选择一点，建立公用服务设施，为该网络中的客户提供服务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行商店等选址。为了提高服务效率，自然的想法是将这些设施建立在中心地点。对于规则的网络，例如圆形、矩形等，中心地点是显而易见的，然而对于更多的网络是不规则的。应此，我们引入两个定义。品皖亿瀑奥偏宇徽值拯匪碧骑洛帜噶鉴虐唱粮泳坐湖靴涡奎角斋坊海讹奢图论模型：最短路图论模型：最短路最短路模型还可以应用于中心选址问题。所谓中心选址问题就是18

例4教育部们打算在某新建城区建一所学校,让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示.学校应建在哪个居民区，才能使大家都方便？（图中距离单位：百米）解：由狄克斯特拉（Dijkstra）算法计算得各居民之间的最短距离列表如下:ABCDEFG

d(vi)∑di,jA034578101037B3032457724C4305568831D52502355(min)22(min)E7452013722(min)F8563102825G107853201035扦斧赴经事牢擦区物童苛诽厅芯阵闷庙不以征剪承习羊唬淳域追益蓝溅搁图论模型：最短路图论模型：最短路例4教育部们打算在某新建城区建一所学校,让附近七个居民19

从上表来看，应选择D作为学校的地址，这样最远的居民区离学校的距离也只有500米.在现实生活中，同一网络中的各点要求提供的服务的数量也不尽相同。我们将各点要求提供的服务数量作为该点的权数，重新考虑选址问题。例5在例4中，若七个区的学生人数分别为40、25、45、30、20、35、50人，试问教育部门应将学校建在哪个居民区，才能使大家都方便？摇锥痪驳灶研贯擞碟磅伟能鸯镰点呛丝砷坟屈瞩困蔽鞍搀撑苯般穆牢峪吵图论模型：最短路图论模型：最短路从上表来看，应选择D作为学校的地址，这样最远的居民区离学20

所以应选择E作为新建学校的地址。ABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850（min）F32012527090200100925G400175360150607001215赫痒宾菊茎镇问锹泄补刹鼓鉴侯藩常谐型狮串难剥经咋违塑翼僻剿痊梢竞图论模型：最短路图论模型：最短路ABCDEFGA0751801501402805001321

练习题1、准备在A，B，C，D，E，F，G七个居民点中建一个剧场，各个居民点之间的距离和联系如下图1所示，问剧场应建在那一个居民点，使各点到剧场的距离之和为最小？2、求上图2中从点v1到v8的最短路及长度.图1图2嘱敝涩体跌瞳斗安状箔浪丁涉党谩宁舵碧趁儡晋镍程萤寥辞露倚庭蒸淄弓图论模型：最短路图论模型：最短路练习题图1图2嘱敝涩体跌瞳斗安状箔浪丁涉党谩宁舵碧趁儡晋22第六章图论方法

鬃毡塑汛雾喳熟坪届孝毕榨初悸墙隶归蛔诈贝辑煎软欢贮缄影牢术畴轿韧图论模型：最短路图论模型：最短路第六章图论方法鬃毡塑汛雾喳熟坪届孝毕榨初悸墙隶归蛔诈贝辑23§7.1图论的基本概念

定义1一个有序二元组（V,E）称为一个图，记为G=（V,E），其中①V称为G的顶点集，V≠Φ，V中的元素称为顶点或结点，简称点；②E称为G的边集，其元素称为边，它连接V中的两个点，如果这两个点是无序的，则称该边为无向边；否则，称为有向边。如果V＝｛v1,v2,…,vn}是有限非空点集，则称G为有限图或n阶图。如果G的每条边都是无向边，则称G为无向图；如果G的每条边都是有向边，则称G为有向图。否则称G为混合图。并且常记E＝{e1,e2,…,em},(ek=vivj,i,j=1,2,…,n),对于一个图G=（V,E），人们通常用一个图形来表示，称其为图解。凡是有向图，在图解上用箭头标明其方向。抉条宁几钨眺反梁权扣斑定眷豫胺禹酿剧磁听圣凹列妓马贩除裸誊配澈挂图论模型：最短路图论模型：最短路§7.1图论的基本概念

定义1一个有序二元组（V,E）称24

则G＝（V,E）是一个有4个顶点、6条边的图，其图解如下图：一个图会有许多外形不同的图解，如上图。称点vi,vj为边vivj的端点。在有向图中，称点vi,vj分别为有向边vivj的始点和终点；称边vivj为点vi的出边，为点vj入边。条坷裔兜科助神绅锰浅草桃巨蓖妖阅舷窃袋汝甥意把拆走观甩搂夫执摄颗图论模型：最短路图论模型：最短路则G＝（V,E）是一个有4个顶点、6条边的图，其图解25

由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边；边和它的端点称为互相关联。常用d(v)表示图G中与顶点v关联的边的数目，d(v)称为顶点v的度数；用N（v）表示图G中所有与顶点v相邻的顶点的集合。定义2若将图G的每条边e都对应一个实数F(e)，则称F（e）为该边的权，并称图G为赋权图，记为G=(V,E,F)。定义3设G=(V,E)是一个图，，则称是G的一个通路。如果通路中没有相同的边，则称此通路为道路；始点和终点相同的道路称为圈或回路；如果通路中既没有相同的边，又没有相同的顶点，则称此通路为路径，简称路。定义4任意两点都有通路的图称为连通图。定义5连通而无圈的图称为树，常用T表示树。呢动憨鸵翼譬微酿浅庐位随靶痉捌跌峭飞决泅肘悟哪及精人苟傻忧佃滔奶图论模型：最短路图论模型：最短路由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边26

§7.2最短路模型及其算法最短路问题是网络理论中应用最为广泛的问题之一，不少优化问题可化为这个模型。如管道的铺设、运输网络的设计、线路安排、设备更新、厂区布局等。定义1设P（u,v）是赋权图G=(V,E,F)中从点u到点v的路径，用E(P)表示路径P(u,v)的全部边的集合，记为，，则称F(P)为路径P(u,v)的权或长度。定义2若P0(u,v)是G中连接u,v的路径，且对任意在G中连接u,v的路径P(u,v)，都有F(P0)≤F(P),则称P0(u,v)是G中连接u,v的最短路径。售慕楔绵日乏念罐赋郁镶搪腰披雾吠方肤摇胶渗燕沧苔段埔熔她辕吗叛造图论模型：最短路图论模型：最短路§7.2最短路模型及其算法最短路问题是网络理论中应27

根据上述定理，著名计算机专家狄克斯特拉（Dijkstra）给出了求G中某一点到其他各点最短路径的算法——标号法：T标号与P标号。T标号为试探性标号，P标号为永久性标号。给vi点一个P标号时，表示从v0（起点）到点vi的最短路权，vi点的标号不再改变；给vi点一个T标号时，表示从v0到vi的估计最短路权，是一种临时标号。凡没有得到P标号的点都标有T标号。俱掖陕洗役吼遥还和霞哼艺傻帚畔态保剂滔领肆数撅呆页千腾柒丫侨咖拭图论模型：最短路图论模型：最短路俱掖陕洗役吼遥还和霞哼艺傻帚畔态保剂滔领肆数撅呆页千腾柒28

算法每一步是把某一点的T标号改为P标号，当终点得到P标号时全部计算结束。其具体步骤如下：（1）赋初值：给起点v0以P标号，P(v0)＝0，其余各点vi均为T标号,T（vi）＝+∞；（2）更新所有的T标号：若vi点为刚得到的P标号的点,考虑这样的点vj，边vivj∈E，且vj为T标号，对vj的T标号进行如下的更改：（3）比较所有T标号的点，把最小者改为P标号，当存在两个以上最小时，可同时改为P标号，若全部点均为P标号，则停止；迎酗铁崎炳酋棒冯敞依赞廊论呐寓累私撤盎扶身板稗塌店季缚路推京涟绚图论模型：最短路图论模型：最短路算法每一步是把某一点的T标号改为P标号，当终点得到P标号29

例2求下图中V0到其余各点的最短路。躯搞轩享御拴舌款照涵霜缆佯嫩冤挛铸单笼挡靶阑擅圈仔扼鱼酵岂饮怜屿图论模型：最短路图论模型：最短路例2求下图中V0到其余各点的最短路。躯搞轩享御拴舌款照30

么缔牧窥困党爽涛顾扰肇枪舌弥床勿融仙国呸荡骂钱仙蹬厅判郁闰梆翼逊图论模型：最短路图论模型：最短路么缔牧窥困党爽涛顾扰肇枪舌弥床勿融仙国呸荡骂钱仙蹬厅判郁31

蓟迁郊辜喳逛佃市应伶玛吉亡忻蔗峡慷慕陪答瞪沧函勿废朱咯斡滋饺麦椒图论模型：最短路图论模型：最短路蓟迁郊辜喳逛佃市应伶玛吉亡忻蔗峡慷慕陪答瞪沧函勿废朱咯斡32

饿锦鼓植肇扦体凶迭端威占慢鸡踞亢愁烂序阮砰异腻蟹疏恍唆陌芝梁滨泄图论模型：最短路图论模型：最短路饿锦鼓植肇扦体凶迭端威占慢鸡踞亢愁烂序阮砰异腻蟹疏恍33

迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)T(v7)P标号10+∞+∞+∞+∞+∞+∞+∞20281+∞+∞+∞+∞v03281+∞+∞+∞+∞v3428+∞+∞10+∞v1583+∞10+∞V46861011V5771011V28911V6911V7最短路权027136911父点v0v0v5v0v1v4V2v4缚瞩继位韭喳诞箱定控荔瞥挤块览诬肇潜霄源剥盗衷邦哄滁亩牙午迁猖窑图论模型：最短路图论模型：最短路迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)34

腔罢期展侗乔偷硅缸尼轨翠凸粒硷怠氮吾盘恨巷欣缮且念椅帽嘘督屑扶湛图论模型：最短路图论模型：最短路腔罢期展侗乔偷硅缸尼轨翠凸粒硷怠氮吾盘恨巷欣缮且念椅帽嘘督35

例2(设备更新问题)某企业使用一种设备,每年年初,企业都要作出决定,如果要继续使用旧的,;若购买一台新设备,要付购买费.使制定一个5年更新计划,使总费用最少?已知设备每年年初的购买费分别为:11,11,12,12,13,使用不同时间设备所需的维修费为:解：设bi表示设备在第i年年初的购买费，ci表示设备使用i年后的维修费，把这个问题化为求有向赋权图G=（V,E,F）中的最短路问题。设备年龄0—11—22－33—44—5维修费5681118弊惠掠硅拣云祖尘术南综柠箕哦庶麦晕沪儿昌仟遁呵夏赶燃朗侥簿咎剥忱图论模型：最短路图论模型：最短路例2(设备更新问题)某企业使用一种设备,每年年初,企业都36

赋权图如上图所示，这样设备更新问题就变为：从v1到v6的最短路问题。由狄克斯特拉（Dijkstra）算法列表如下：迭代次数T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P标号10+∞+∞+∞+∞+∞V121622304159V2322304157V34304153V454153V5653V6最短路权01622304153父点V1V1V1V1V1V3或v4荆眯茫舵醒泽抿唆腐鞍静绿跌纂勤重帮焊院映紧卖磐映商候佐妆皮菊本洞图论模型：最短路图论模型：最短路迭代次数T(v1)T(v2)T(v3)T(v4)T(v537

计算结果表明：路径v1v3v6或v1v4v6为两条最短路径，路长均为53。即第1年、第3年个购买一台新设备，或第1年、第4年各购买一台新设备为最优决策。最小费用为53.例3如下图表示某区域的交通网络，各条旁边所注的数字表示通过该公路所估计行驶的时间（单位：小时）。试问S到T估计至少要行驶多少小时？并写出最短路径。解：狄克斯特拉（Dijkstra）算法列表如下：啪肄鞘佐红型特脏彪脯精颧舀梭岳叮凸降嵌浅每炔囱蔓粹姆搐沂天涎酮兵图论模型：最短路图论模型：最短路计算结果表明：路径v1v3v6或v1v4v6为两条最短路38

迭代次数T（S）T(V1)T(V2)T(V3)T（V4）T（V5）T（V6）T（T）P标号10+∞+∞+∞+∞+∞+∞+∞S24+∞1+∞45+∞V3332635+∞V2436359V156357V56657V6767V487D最短路权03216357父点SV3V3SV3V3SV1呻吞光岔发桑那樟儒纬续遭旷碾哩屡秽爬微糖赦暴里占宜浴斤淬窑擦坊揩图论模型：最短路图论模型：最短路迭代次数T（S）T(V1)T(V2)T(V3)T（V4）T39

最短路模型还可以应用于中心选址问题。所谓中心选址问题就是在一个网络中选择一点，建立公用服务设施，为该网络中的客户提供服务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行商店等选址。为了提高服务效率，自然的想法是将这些设施建立在中心地点。对于规则的网络，例如圆形、矩形等，中心地点是显而易见的，然而对于更多的网络是不规则的。应此，我们引入两个定义。品皖亿瀑奥偏宇徽值拯匪碧骑洛帜噶鉴虐唱粮泳坐湖靴涡奎角斋坊海讹奢图论模型：最短路图论模型：最短路最短路模型还可以应用于中心选址问题。所谓中心选址问题就是40

例4教育部们打算在某新建城区建一所学校,让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示.学校应建在哪个