图与网络优化.ppt

图与网络优化图与网络优化 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题本章内容重点2引引 言言图论应用非常广泛：图论应用非常广泛：控控制制论论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等领领域；域；科科学学研研究究，市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以用用图图论论的的理理论论和和方方法法来加以解决。来加以解决。例例如如，通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合理布局。合理布局。3引引 言言将将复复杂杂的的工工程程系系统统和和管管理理问问题题用用图图的的理理论论加加以以描描述述，可可以以解解决决许许多多工工程程项项目目和和管管理理决决策策的优化问题。的优化问题。图图论论越越来来越越受受到到工工程程技技术术人员和经营管理人员的重视。人员和经营管理人员的重视。4引引 言言 17361736年年瑞瑞士士科科学学家家欧欧拉拉发发表表了了关关于于图图论论方方面面的的第第一一篇篇科科学学论论文文，解决了著名的哥尼斯堡七座桥问题。解决了著名的哥尼斯堡七座桥问题。德德国国的的哥哥尼尼斯斯堡堡城城有有一一条条普普雷雷格格尔尔河河，河河中中有有两两个个岛岛屿屿，河河的的两两岸岸和和岛岛屿屿之之间间有有七七座座桥桥相相互互连连接接，如图如图8-1a8-1a所示。所示。5引引 言言AB图8-1 a）CD6引引 言言 当当地地的的居居民民热热衷衷于于这这样样一一个个问问题题，一一个个漫漫步步者者如如何何能能够够走走过过这这七七座座桥桥，并并且且每每座座桥桥只只能能走走过过一一次次，最最终终回回到到原原出出发发地地。尽管试验者很多，但是都没有成功。尽管试验者很多，但是都没有成功。为为了了寻寻找找答答案案，17361736年年欧欧拉拉将将这这个个问问题题抽抽象象成成图图8-1b8-1b所所示示图图形形的的一一笔笔画画问问题题。即即能能否否从从某某一一点点开开始始不不重重复复地地一一笔笔画画出出这这个个图图形形，最最终终回回到到原原点点。欧欧拉拉在在他他的的论论文文中中证证明明了了这这是是不不可可能能的的，因因为为这这个个图图形形中中每每一一个个顶顶点点都都与与奇奇数数条条边边相相连连接接，不不可可能能将将它它一一笔笔画画出出，这这就就是是古古典典图图论论中中的的第第一一个著名问题。个著名问题。7引引 言言图8-1 b）ACDB8例例4 4 中国邮递员问题中国邮递员问题（CPPChinesepostmanproblem）一一名名邮邮递递员员负负责责投投递递某某个个街街区区的的邮邮件件。如如何何为为他他（她她）设设计计一一条条最最短短的的投投递递路路线线（从从邮邮局局出出发发，经经过过投投递递区区内内每每条条街街道道至至少少一一次次，最最后后返返回回邮邮局局）？由由于于这这一一问问题题是是我我国国管管梅梅谷谷教教授授19601960年年首首先先提提出出的的，所所以以国国际际上上称称之之为为中中国国邮递员问题。邮递员问题。9例例5 5 旅行商问题（哈密顿问题）旅行商问题（哈密顿问题）（TSPtravelingsalesmanproblem）一一名名推推销销员员准准备备前前往往若若干干城城市市推推销销产产品品。如如何何为为他他（她她）设设计计一一条条最最短短的的旅旅行行路路线线（从从驻驻地地出出发发，经经过过每每个个城城市市恰恰好好一一次次，最最后后返返回回驻驻地地）？这这一一问问题题的的研研究究历历史史十十分分悠悠久久，通通常常称之为旅行商问题。称之为旅行商问题。10 在在实实际际的的生生产产和和生生活活中中，人人们们为为了了反反映映事事物物之之间间的的关关系系，常常常常在在纸纸上上用用点和线来画出各式各样的示意图。点和线来画出各式各样的示意图。例例8.1:8.1:图图8-28-2是是我我国国北北京京、上上海海、重重庆庆等等十十四四个个城城市市之之间间的的铁铁路路交交通通图图，这这里里用用点点表表示示城城市市，用用点点与与点点之之间间的的线线表表示示城城市市之之间间的的铁铁路路线线。诸诸如如此此类类还还有有城城市市中中的的市市政政管管道道图图，民民用用航航空空线图等等。线图等等。1.1.图的基本概念与基本定理图的基本概念与基本定理111.1.图的基本概念与基本定理图的基本概念与基本定理太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京图8-212 例例8.2:8.2:有有六六支支球球队队进进行行足足球球比比赛赛，我我们们分分别别用用点点v v1 1vv6 6表表示示这这六六支支球球队队，它它们们之之间间的的比比赛赛情情况况，也也可可以以用用图图反反映映出出来来，已已知知v v1 1队队战战胜胜v v2 2队队，v v2 2队队战战胜胜v v3 3队队，v v3 3队队战战胜胜v v5 5队队，如如此此等等等等。这这个个胜胜负负情情况况，可可以以用用图图8-38-3所所示示的的有有向向图图反反映映出出来。来。1.1.图的基本概念与基本定理图的基本概念与基本定理131.1.图的基本概念与基本定理图的基本概念与基本定理v3v1v2v4v6v5图8-314 图图论论中中常常用用点点和和点点之之间间的的线线所所构构成成的的图图，反反映映实实际际生生产产和和生生活活中中的的某某些些特特定定对对象象之之间间的的特特定定关关系系。一一般般来来说说，通通常常用用点点表表示示研研究究对对象象、用用点点与与点点之之间间的的线线表表示示研研究对象之间的特定关系究对象之间的特定关系。在在一一般般情情况况下下，图图中中的的相相对对位位置置如如何何，点点与与点点之之间间线线的的长长短短曲曲直直，对对于于反反映映研研究究对象之间的关系，显的并不重要。对象之间的关系，显的并不重要。因因此此，图图论论中中的的图图与与几几何何图图，工工程程图图等本质上是不同的。等本质上是不同的。1.1.图的基本概念与基本定理图的基本概念与基本定理15 通通常常把把点点与与点点之之间间不不带带箭箭头头的的线线叫叫做做边边，带箭头的线叫做，带箭头的线叫做弧弧。如如果果一一个个图图是是由由点点和和边边所所构构成成的的，那那么么，称称为为为为无无向向图图，记记作作G=(V，E)，其其中中V表表示示图图G的的点点集集合合，E表表示示图图G的的边边集集合合。连连接接点点vi,vjV的的边边记记作作vi,vj，或或者者vj,vi。如如果果一一个个图图是是由由点点和和弧弧所所构构成成的的，那那么么称称为为它它为为有有向向图图，记记作作D=(V,A)，其其中中V 表表示示有有向向图图D的的点点集集合合，A表表示示有有向向图图D的的弧弧集集合合。一一条条方方向向从从vi指指向向vj的的弧弧，记记作作(vi,vj)。16例如例如.图图8-4是一个无向图是一个无向图G=（V，E）其中其中V=v1,v2,v3,v4E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v31.1.图的基本概念与基本定理图的基本概念与基本定理v3v2v1v4图图8-48-417图图8-5是一个有向图是一个有向图D=（V，A）其中其中V=v1,v2,v3,v4,v5,v6,v7A=(v1,v2),(v1,v3),(v3,v2),(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)1.1.图的基本概念与基本定理图的基本概念与基本定理v7v5v3v4v2v1v6图图8-58-518一些常用的名词：无向图一些常用的名词：无向图G G 或或 有向图有向图D Dw节点数节点数 记作记作P(G)P(G)或或P(D)P(D),简记作简记作P P,w边边数数 或或者者 弧弧数数 记记作作q(G)q(G)或或者者q(D)q(D),简简记作记作q q。w如如果果边边 v vi i,v,vj j E E,那那么么称称v vi i,v,vj j是是边边的的端端点点，或者，或者v vi i,v,vj j是是相邻相邻的。的。w如如果果一一个个图图G G中中，一一条条边边的的两两个个端端点点是是相相同的同的,那么称为这条边是那么称为这条边是环环。1.1.图的基本概念与基本定理图的基本概念与基本定理191.1.图的基本概念与基本定理图的基本概念与基本定理w如如果果两两个个端端点点之之间间有有两两条条以以上上的的边边，那那么称为它们为么称为它们为多重边多重边。w一个无环，无多重边的图为一个无环，无多重边的图为简单图简单图。w一个无环，有一个无环，有多重边的图称为多重边的图称为多重图多重图。v3v2v1v4图图8-48-4环环20w以以点点v为为端端点点的的边边的的个个数数称称为为点点v 的的度度，记记 作作 d(v)。如如 上上 图图 中中 d(v1)=3,d(v2)=4,d(v3)=4,d(v4)=3。w 度度为为零零的的点点称称为为弧弧立立点点，度度为为1 1的的点点称称为为悬悬挂挂点点。悬悬挂挂点点的的边边称称为为悬悬挂挂边边。w 度度为为奇奇数数的的点点称称为为奇奇点点，度度为为偶偶数数的点称为的点称为偶点偶点。1.1.图的基本概念与基本定理图的基本概念与基本定理21端点的度端点的度d(v)：点：点v作为边端点作为边端点的个数；的个数；奇点奇点：d(v)=奇数；奇数；偶点：偶点：d(v)=偶数；偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边；与悬挂点连接的边；孤立点：孤立点：d(v)=0；空图：空图：E=，无边图，无边图1.1.图的基本概念与基本定理图的基本概念与基本定理22 定理8.1 所有顶点次数之和等于所有边数的2倍。定理8.2 在任一图中，奇点的个数必为偶数。1.1.图的基本概念与基本定理图的基本概念与基本定理23图的连通性：图的连通性：w链：链：由两两相邻的点及其相关联由两两相邻的点及其相关联的边构成的点边序列的边构成的点边序列;如如:v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn;v0，vn分别为链的起点和终点；分别为链的起点和终点；w简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；w初等链：初等链：链中所含的点均不相同链中所含的点均不相同,也称通路；也称通路；1.1.图的基本概念与基本定理图的基本概念与基本定理24回路：回路：若若v0 vn分称该链为开链，否分称该链为开链，否则称为闭链或回路；则称为闭链或回路；圈：圈：除起点和终点外链中所含的点均除起点和终点外链中所含的点均不相同的闭链；不相同的闭链；连通图：连通图：图中任意两点之间均至少有图中任意两点之间均至少有一条通路，否则称作不连通图。一条通路，否则称作不连通图。1.1.图的基本概念与基本定理图的基本概念与基本定理25子图：子图：设设G1=V1,E1,G2=V2,E2w子图定义：子图定义：如果如果V2 V1,E2 E1称称 G2是是G1 的子图；的子图；w真子图：真子图：如果如果V2 V1,E2 E1称称G2是是G1的真子图；的真子图；w部分图（支撑子图）：部分图（支撑子图）：如果如果V2=V1,E2 E1称称G2是是G1的部分图；的部分图；w导出子图：导出子图：若若V2 V1,E2=vi,vj:vi,vj V2,称称G2 是是G1 中由中由V2 导出导出的导出子图。的导出子图。1.1.图的基本概念与基本定理图的基本概念与基本定理27有向图：关联边有方向有向图：关联边有方向弧：弧：有向图的边有向图的边a=(=(u,v),),起点起点u,终点终点v;路：路：若有从若有从 u 到到 v 不考虑方向的链不考虑方向的链,且且 各方向一致各方向一致,则称之为从则称之为从u到到v的路；的路；初等路初等路:各顶点都不相同的路；各顶点都不相同的路；初等回路初等回路:u=v 的初等的初等 路路;连通图：连通图：若不考虑方向若不考虑方向 是无向连通图是无向连通图;强连通图：强连通图：任两点有路任两点有路;1.1.图的基本概念与基本定理图的基本概念与基本定理312.2.树和最小支撑树树和最小支撑树 一、树及其性质一、树及其性质 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简简单单又又非非常常具具有有应应用用价价值值的的图，这就是图，这就是树树。例例8.38.3：已已知知有有六六个个城城市市，它它们们之之间间要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通通话话，并并且且电电话话线线的总长度最短。的总长度最短。322.2.树和最小支撑树树和最小支撑树 如如果果用用六六个个点点v v1 1，v v6 6代代表表这这六六个个城城市市，在在任任意意两两个个城城市市之之间间架架设设电电话话线线，即即在在相相应应的的两两个个点点之之间间连连一一条条边边。这这样样，六六个个城城市市的的一一个个电电话话网网就就作作成成一一个个图图。由由于于任任意意两两个个城城市市之之间间均均可可以以通通话话，这这个个图图必必须须是是连连通通图图。并并且且，这这个个图图必必须须是是无无圈圈的的。否否则则，从从圈圈上上任任意意去去掉掉一一条条边边，剩剩下下的的图图仍仍然然是是六六个个城城市市的的一一个个电电话话网网。图图8-88-8是是一一个个不不含含圈圈的的连连通图，代表了一个电话线网。通图，代表了一个电话线网。332.2.树和最小支撑树树和最小支撑树图8-8v6v3v4v2v5v1342.2.树和最小支撑树树和最小支撑树 定义定义8.1 8.1 无圈的连通图叫做树无圈的连通图叫做树。w 性质：性质：定定理理8.3 8.3 设设图图G=(V，E)是是一一个个树树P(G)2，那那么么图图G中中至至少少有有两两个个悬挂点。悬挂点。定定理理8.4 8.4 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G不不含含圈圈，并并且且有有且仅有且仅有P-1P-1条边条边。352.2.树和最小支撑树树和最小支撑树定定理理8.5图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G是是连连通通图图，并并且且有且仅有有且仅有P-1条边条边。定定理理8.6图图G是是一一个个树树的的充充分分必必要要条条件件是是任任意意两两个个顶顶点点之之间间有有且且仅有一条链仅有一条链。362.2.树和最小支撑树树和最小支撑树从以上定理，不难得出以下结论：从以上定理，不难得出以下结论：（1 1）从从一一个个树树中中任任意意去去掉掉一一条条边边，那那么么剩剩下下的的图图不不是是连连通通图图，亦亦即即，在在点点集集合合相相同同的的图图中中，树树是是含含边数最少的连通图。边数最少的连通图。（2 2）在在树树中中不不相相邻邻的的两两个个点点之之间间加加上上一一条条边边，那那么么恰恰好好得得到到一一个个圈圈。372.2.树和最小支撑树树和最小支撑树 二二.支撑树支撑树定定义义8.2设设图图K=(V,E)是是图图G=(V,E)的的一一支支撑撑子子图图,如如果果图图K=(V,E)是是一一个个树树,那那么称么称K是是G的一个支撑树。的一个支撑树。图图8.10b是图是图8-10a的一个支撑树。的一个支撑树。v6v5v2v3v4v1v6v5v2v3v4v1图8-10a）b）382.2.树和最小支撑树树和最小支撑树w显然显然,如果图如果图K=(V,E)是图是图G=(V,E)的一的一个支撑树个支撑树,那么那么K 的边数是的边数是p(G)-1；wG中不属于支撑树中不属于支撑树K的边构成的边构成K的余树，的余树，其边数是其边数是q(G)-p(G)+1。w定理定理8.7一个图一个图G有支撑树的充要条有支撑树的充要条件是件是G是连通图。是连通图。39证明证明:必要性必要性显然；显然；充分性充分性:设图设图G G是连通的，若是连通的，若G G不含圈，则不含圈，则G G是一个树，从而是一个树，从而G G是自身的一个支撑树。是自身的一个支撑树。若若G G含圈，则任取含圈，则任取G G的一个圈，从该圈的一个圈，从该圈中任意去掉一条边，得到图中任意去掉一条边，得到图G G的一支撑子的一支撑子图图G G1 1。若。若G G1 1不含圈，则不含圈，则G G1 1是是G G的一个支撑树。的一个支撑树。若若G G1 1仍然含圈，则任取仍然含圈，则任取G G1 1的一个圈，再从的一个圈，再从圈中任意去掉一条边，得到图圈中任意去掉一条边，得到图G G的一支撑的一支撑子图子图G G2 2。依此类推，可以得到图。依此类推，可以得到图G G的一个的一个支撑子图支撑子图G GK K，且不含圈，从而，且不含圈，从而G GK K是一个支是一个支撑树。撑树。422.2.树和最小支撑树树和最小支撑树 以上充分性的证明，提供了以上充分性的证明，提供了一个寻找连通图支撑树的方法叫一个寻找连通图支撑树的方法叫做做“破圈法破圈法”。就是从图中任取。就是从图中任取一个圈，去掉一条边。再对剩下一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。时为止，这样就得到一个支撑树。432.2.树和最小支撑树树和最小支撑树w例例8.4:8.4:用破圈法求出下图的一用破圈法求出下图的一个支撑树。个支撑树。V5V4V2V3V1e6e5e4e3e2e1e7e844 取一个圈取一个圈(v1,v2,v3,v1)，在一个圈，在一个圈中去掉边中去掉边e3。在剩下的图中，再取一。在剩下的图中，再取一个圈（个圈（v1,v2,v4,v3,v1），去掉边），去掉边e4。再。再从圈（从圈（v3,v4 v5,v3）中去掉边）中去掉边e6。再从。再从圈圈(v1,v2,v5,v4,v3,v1）中去掉边）中去掉边e7，这，这样，剩下的图不含圈，于是得到一个样，剩下的图不含圈，于是得到一个支撑树，如图所示。支撑树，如图所示。v2e1e2e5e8v1v3v4452.2.树和最小支撑树树和最小支撑树 三、最小支撑树问题三、最小支撑树问题定义定义8.3如果图如果图G=（V，E），对于），对于G中的每一条中的每一条vi,vj，相应地有一个数相应地有一个数wij，那么称这样，那么称这样的图的图G为为赋权图赋权图，wij称为边称为边vi,vj的权。的权。这里所指的权，是具有广义这里所指的权，是具有广义的数量值。根据实际研究问题的的数量值。根据实际研究问题的不同，可以具有不同的含义。例不同，可以具有不同的含义。例如长度，费用、流量等等。如长度，费用、流量等等。462.2.树和最小支撑树树和最小支撑树定义定义8.4如果图如果图T=（V，E）是图是图G 的一个支撑树，那么称的一个支撑树，那么称E上上所有边的权之和为所有边的权之和为支撑树支撑树T 的权的权，记作记作S(T)。如果图如果图G 的支撑树的支撑树T*的权的权S(T*)，在，在G的所有支撑树的所有支撑树T 中的权最小，中的权最小，即即S(T*)=minS(T)，那么称，那么称T*是是G 的的最小支撑树最小支撑树。472.2.树和最小支撑树树和最小支撑树常用的有破圈法和生长法（避圈法）两个方法：（1）在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；（1）去掉该圈中权数最大的边；反复重复（1）（2）两步，直到最短树。482.2.树和最小支撑树树和最小支撑树 例8.5 某六个城市之间的道路网如图8-13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。492.2.树和最小支撑树树和最小支撑树v6v5v2v3v4图8-13av162753544v3v2v1v4v6v5513142图8-13b顺序：顺序：浅兰浅兰，黄黄，粉红粉红，白，白502.2.树和最小支撑树树和最小支撑树 解解：如图：如图8-13a8-13a，用破圈法求解最小支撑树。，用破圈法求解最小支撑树。（1 1）圈圈v1,v2,v3,v1，删圈中权最大边，删圈中权最大边v1,v3；（2 2）圈）圈v3,v5,v2,v3，去掉边，去掉边v2,v5；（3）圈）圈v3,v5,v4,v2,v3，去掉边，去掉边v3,v5；（4）圈）圈v5,v6,v4,v5，这里有两条权最大的边，这里有两条权最大的边v5,v6和和v4,v6。任意删一条，如。任意删一条，如v5,v6。这时得到一个不含圈的图，这时得到一个不含圈的图，即是最小支撑树。即是最小支撑树。如图如图8-13b8-13b所示。所示。512.2.树和最小支撑树树和最小支撑树 从网络图中依次寻找从网络图中依次寻找权数较权数较小的边小的边，寻找过程中，节点不得，寻找过程中，节点不得重复，即重复，即不得构成圈不得构成圈。注意在找。注意在找较小权数边时不考虑已选过的边较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进和可能造成圈的边。如此反复进行，直到得到最短树或证明网络行，直到得到最短树或证明网络不存在最短树。不存在最短树。522.2.树和最小支撑树树和最小支撑树用用“生长法生长法”求解例求解例8.58.5解解：考虑赋权图：考虑赋权图8-13a8-13a，任取一点，如，任取一点，如w 从从v1 取权较小的边（取权较小的边（v1,v2）；）；w从从v2 取取权较小的边（权较小的边（v2,v3）；）；w从从v3 取取权较小的边（权较小的边（v3,v4）；）；w同理依次取（同理依次取（v4,v5），（），（v4,v6）。这时得到了如图这时得到了如图8-13b8-13b所示的最小所示的最小支撑树。支撑树。532.2.树和最小支撑树树和最小支撑树v6v5v2v3v4图8-13av162753544v3v2v1v4v6v5513142图8-13b顺序：顺序：黄黄，粉红粉红，白，白，绿绿，浅兰浅兰54计算机编程whttp:/ 一.引言 最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。563.3.最短路径问题最短路径问题 例例8.6:8.6:如图如图8-148-14所示的单行线交通所示的单行线交通网，每个弧旁边的数字表示这条单行线的网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从长度。现在有一个人要从v v1 1出发，经过这出发，经过这个交通网到达个交通网到达v v8 8，要寻求是总路程最短的，要寻求是总路程最短的线路。线路。图8-14v1v4v2v8v7v6v5v9636234102312624101573.3.最短路径问题最短路径问题 从从v v1 1到到v v8 8的的路路线线是是很很多多的的。比比如如从从v v1 1出出发发，经经过过v v2 2,v v5 5到到达达v v8 8或或者者从从v v1 1出出发发，经经过过v v4 4，v v6 6，v v7 7到到达达v v8 8等等等等。但但不不同同的的路路线线，经经过过的的总总长长度度是是不不同同的的。例例如如，按按照照第第一一个个线线路路，总总长长度度是是6+1+6=136+1+6=13单单位位，按按照照第第二二个个路路线线，总总长长度度是是1+10+2+4=171+10+2+4=17单位。单位。58 一般意义下的最短路问题：一般意义下的最短路问题：设设赋赋权权有有向向图图D=（V，A），对对每每个个弧弧a=（vi,vj），相相应应地地有有权权wij。vs,vt是是D中中的的两两个个顶顶点点，P是是D中中从从vs到到vt的的任任意意一一条条路路，定定义义路路的的权权是是P中中所所有有弧弧权权的的和和，记记作作S(p)。最最短短路路问问题题就就是是求求S(P0)=minS(p)。P0叫叫做做从从vs到到vs的的最最短短路路。P0的的权权S(P0)叫叫做做从从vs到到vt的的距离距离，记作，记作d（vs，vt）。由由于于D是是有有向向图图，很很明明显显d（vs，vt）与与d（vt，vs）一般不相等。）一般不相等。593.3.最短路径问题最短路径问题 二、二、Dijkstra（狄克斯拉方法狄克斯拉方法）算法）算法 下下面面介介绍绍在在一一个个赋赋权权有有向向图图中中寻寻求求最最短短路路的的方方法法DijkstraDijkstra算算法法，它它是是在在19591959年年提提出出来来的的。目目前前公公认认，在在所所有有的的权权 wij00时时，这这个个算算法法是是寻寻求求最最短短路路问问题题最最好好的的算算法法。并并且且，这这个个算算法法实实际际上上也也给给出出了了寻寻求求从从一一个个始始定定点点vs到到任任意意一一个个点点vj的的最最短短路路。60 Dijkstra算法的基本思想算法的基本思想 从从v vs s出发，逐步向外寻找最短路。在出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，运算过程中，与每个点对应，记录一个数，叫做一个点的叫做一个点的标号标号,分为两类：分为两类：P P 标号：标号：表示从表示从v vs s到该点的最短路权到该点的最短路权T T 标号：标号：表示从表示从v vs s到该点最短路权的上界。到该点最短路权的上界。算法的每一步是去修改算法的每一步是去修改T T 标号，把某标号，把某一个具有一个具有T T 标号的点改变为具有标号的点改变为具有P P 标号的标号的点，使图点，使图D D 中具有中具有P P 标号的顶点多一个。标号的顶点多一个。这样，至多经过这样，至多经过P P-1-1步，就可求出从步，就可求出从v vs s到到各点各点v vj j的最短路。的最短路。61说明：说明：在例在例8.68.6中中 S=1。因因为为wij0，d(v1,v1)=0。这这时时，v1是具有是具有P标号的点。标号的点。再再看看从从v1出出发发的的三三条条弧弧(v1,v2)，(v1,v3)和和(v1,v4)。如如果果从从v1出出发发沿沿(v1,v2)到到达达v2，这时的路程是这时的路程是d(v1,v1)+w12=6单位；单位；如如果果从从v1出出发发，沿沿(v1,v3)到到达达v3，则则是是d(v1,v1)+w13=3单位；单位；同同理理，如如果果从从v1出出发发沿沿(v1,v4)到到达达v4，是是d（v1,v1）+w14=1单位。单位。62说明（续）因因此此，从从v v1 1出出发发到到达达v v4 4的的最最短短路路必必是是（v v1 1,v,v4 4），d d（v v1 1,v,v4 4）=1=1。这这是是因因为为从从v v1 1到到达达v v4 4的的任任一一条条路路，假假如如不不是是（v v1 1,v,v4 4），则则必必先先沿沿（v v1 1,v,v2 2）到到达达v v2 2，或或者者沿沿（v v1 1,v,v3 3）到到达达v v3 3，而而这这时时的的路路程程已已是是6 6或或者者3 3单单位位。由由于于w wijij 00，因因此此不不论论他他如如何何再再从从v v2 2或或者者v v3 3到到达达v v4 4，所所经经过过的的总总路路程程都都不不会会比比1 1少少，于于是是就就有有d d（v v1 1,v,v4 4）=1=1。于于是是V4 4变变成成具具有有P P标标号的点。号的点。63例例8.6说明：说明：从从v1出发的三条弧出发的三条弧(v1,v2)，(v1,v3)和和(v1,v4)，mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14=d（v1,v4）=1。P(V4)v2v8v7v6v5v963623410231262410P(V1)164 再再看看从从v v1 1和和v v4 4指指向向其其余余点点的的弧弧：从从V V1 1出出发发，分分别别沿沿(v1,v2),(v1,v3)到到达达v2，v3，经经过过的的路路程程是是6或或者者3单单位位；从从v4出出发发沿沿(v4,v6)到到达达v6，经经过过的的路路程程是是d(v1,v4)+w46=1+10=11单位。而单位。而mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3单位。单位。根根据据同同样样的的理理由由，可可以以断断定定，从从v1到到达达v3的的最最短短路路是是（v1,v3），d（v1,v3）=3。这这样样，又又使使点点v3 3变变为为具具有有P P 标标号号的的点点，不不断断重重复复以以上上过过程程，就就可可以以求求出出从从vs到到达达任任一点一点vj的最短路。的最短路。65例例8.68.6说明（续）：说明（续）：w再看从再看从v1和和v4指向其余点的弧指向其余点的弧,mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)1663.3.最短路径问题最短路径问题 在在下下述述的的Dijkstra算算法法中中，以以P P，T T 分分别别表表示示某某一一个个点点的的P P 标标号号，T T 标标号号。S Si i表表示示在在第第i i步步时时，具具有有P P 标标号号点点的的集集合合，为为了了在在算算出出从从v vs s到到各各点点的的距距离离的的同同时时，也也找找出出从从v vs s到到各各点点的的最最短短路路，于于是是，给给每每一一个个点点v v一一个个值值。当当算算法法结结束束时时，如如果果(v)(v)=m m，则则表表示示在在从从v vs s到到v v 的的最最短短路路上上，v v 的的前前一一个个点点是是v vm m。如如果果(v v)=)=M M，则则表表示示在在图图D D 中中不不含含有有从从v vs s 到到达达v v 的的路路。(v)(v)=0=0，表示，表示v v=v vs s。67DijkstraDijkstra算法的步骤如下：算法的步骤如下：w开始（开始（i=0）令令S0=vs，P（vs）=0，(vs)=0，对对每每一一个个v vs，令令T（v）=+，(v)=M，令令k=s；w（1）如如果果Si=V，则则算算法法结结束束，对对每每一一个个v Si，d（vs,v）=P（v）。否则转入（）。否则转入（2）；）；w（2）考考察察每每一一个个使使(vk,vj)A，且且vj Si的的点点vj，如如果果T(vj)P(vk)+wkj，则则把把T(vj)改改变变为为P(vk)+wkj，把把(vj)改改变变为为k，否否则则转转入入（3）；）；683.3.最短路径问题最短路径问题w（3）令令T(vji)=minT(vj)vj Si，如果，如果T(vji)+，则把，则把vji的的T 标标号改变为号改变为P 标号标号P(vji)=T(vji)，令，令Si+1=Sivji，k=ji，把，把i换成换成i+1，转入（转入（1）；否则结束。）；否则结束。w这时，对这时，对v Si，d(vs,v)=P(v)；对对v Si，d(vs,v)=T(v)。693.3.最短路径问题最短路径问题用用Dijkstra算法求解例算法求解例8.6。vs为起点为起点:w开开始始,s=1,i=0;S0=v1,P(v1)=0,(v1)=0,T(vi)=+,(vi)=M,i=2,3,9,k=1。w(2)(v1,v2)A，v2 S0，P(v1)+w12w32+P(v3)，将，将T(v2)改变为改变为P(v3)+w32=5,(v2)改变为改变为3。w（3）在在所所有有的的T标标号号中中，T(v2)=5最最小小，于是令于是令P(v2)=5，S3=v1,v4,v3，k=2。i=3：w（2）将将T(v5)改改变变为为P(v2)+w25=6，(v5)改变为改变为2。w（3）在在所所有有的的T标标号号中中，T(v5)=6最最小小，于是令于是令P(v5)=6，S4=v1,v4,v3，k=5。723.3.最短路径问题最短路径问题w（2）将）将T(v6)，T(v7)，T(v8)分别改变为分别改变为10,9，12，将，将(v0)，(v7)，(v8)改变为改变为5。w（3）在在所所有有的的T标标号号中中，T(v7)=9最最小小，于是令于是令P(v7)=9，S5=v1,v4,v3,v2,v5,v7，v=7。i=5：w（2）（）（v7,v8）A，v8 S5，但是，但是T(v8)w78+P(v7)，故，故T(v8)不变。不变。w（3）在在所所有有的的T标标号号中中，T(v6)=10最最小小，于是于是,令令P(v6)=10，S6=v1,v4,v3,v2,v5,v7,v6，k=6。733.3.最短路径问题最短路径问题i=6：w（2）从从v6出出发发没没有有弧弧指指向向不不属属于于S6的的点点，因此转入（因此转入（3）。）。w（3）在在所所有有的的T标标号号中中，T(v8)=12最最小小，令令 P(v8)=12，S7=v1,v4,v3,v2,v5,v7,v6,v8，k=8。i=7：w仅仅有有T标标号号的的点点为为v9，T（v9）=+，算算法结束。法结束。此此时时，把把P标标号号和和值值标标在在图图中中，如如图图8-15所示所示74例题求解图示（例题求解图示（1 1）v4v2v8v7v6v5v963623410231262410图图8-158-15T(V6)=+T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=M(V5)=MT(V2)=6T(V5)=+T(V8)=+(V7)=M(V2)=1(V8)=MT(V9)=+(V9)=MT(V3)=3(V3)=11i=0 S1=S0v4=v1,v4v1v375例题求解图示（例题求解图示（2 2）v4v2v8v7v6v5v963623410231262410图图8-158-15T(V6)=11T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=MT(V2)=6T(V5)=+T(V8)=+(V7)=M(V2)=1(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i=1 S2=S1v3=v1,v4,v3v1v376例题求解图示（例题求解图示（3 3）v4v2v8v7v6v5v963623410231262410图图8-158-15T(V6)=11T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=MP(V2)=5T(V5)=+T(V8)=+(V7)=M(V2)=3(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i=2 S3=S2v2=v1,v4,v3,v2v1v377例题求解图示（例题求解图示（4 4）v4v2v8v7v6v5v963623410231262410图图8-158-15T(V6)=11T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=2P(V2)=5P(V5)=6T(V8)=+(V7)=M(V2)=3(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i=3 S4=S3v5=v1,v4,v3,v2,v5v1v378例题求解图示（例题求解图示（5 5）v4v2v8v7v6v5v963623410231262410图图8-158-15T(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6T(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11i=4 S5=S4v7=v1,v4,v3,v2,v5,v7v1v379例题求解图示（例题求解图示（6 6）v4v2v8v7v6v5v963623410231262410图图8-158-15P(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6T(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11i=5 S6=S5v6=v1,v4,v3,v2,v5,v7,v6v1v380例