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