《《运筹学教学资料》运筹学第10-11章.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第10-11章.ppt（198页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、China University of Mining and Technology运筹学Chapter10图与网络分析图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：China University of Mining and Technology-2-运筹学学习要点：学习要点：1.掌握一般图论及其基本概念；掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；能够应用最短路算法求解实际问题；3.掌
2、握最大流最小割理论。掌握最大流最小割理论。China University of Mining and Technology-3-运筹学18世纪，世纪，Knigsberg是俄罗斯的一个城市（现为加里宁格勒）。市内是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次能否从某处出发，经过每座桥一次且恰好一次又回到出发点？且恰好一次又回到出发点？”1736年，年，Euler巧妙地将此问巧妙地将此问题化为图的不题化为图的不重复重复一笔画问一笔画问题题，并证明了，并证明了该问题不存在该问题不存在肯定回答，发肯定回答，发表了第一
3、篇论表了第一篇论文。文。七桥问题七桥问题七桥问题七桥问题图图的的基基本本概概念念与与模模型型China University of Mining and Technology-4-运筹学 中国邮路问题中国邮路问题中国邮路问题中国邮路问题一一邮邮递递员员送送信信，要要走走完完他他所所负负责责的的全全部部街街道道分分送送信信件件，最最后后返返回回邮邮局局。邮邮递递员员都都会会本本能能地地以以尽尽可可能能少少的的行行程程完成送信任务。如何走路线最短。完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为年，由我国数学家管梅谷提出，国际上称为中国邮中国邮递员问题递员问题。问题问题
4、：求一个圈，过每边至少一次，并使圈的长度最短。：求一个圈，过每边至少一次，并使圈的长度最短。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-5-运筹学HamiltonHamilton图图图图游戏：游戏：用正十二面体上用正十二面体上20个顶点表示个顶点表示20个城市，要求参加游个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。出发城市。问题问题：如何判断一个图是否具有：如何判断一个图是否具有这样的性质。如果有，这样的行这样的性质。如果有，这样的
5、行走路线如何确定。走路线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一显然这样的路线存在且不唯一显然这样的路线存在且不唯一显然这样的路线存在且不唯一图图的的基基本本概概念念与与模模型型China University of Mining and Technology-6-运筹学50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一个棋盘中，若马（马走日步）能否从某
6、一点出发跳遍棋盘上在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于每一点恰好一次，再回到出发点？对于44，55，或，或88的的棋盘上马的跳动如何？棋盘上马的跳动如何？图图的的基基本本概概念念与与模模型型China University of Mining and Technology-7-运筹学 幻方问题幻方问题幻方问题幻方问题图图的的基基本本概概念念与与模模型型China University of Mining and Technology-8-运筹学某团体某团体举行舞会，其中有举行舞会，其中有n 个男士与个男士与n 个女士，每个男个女士，每个男士
7、恰好认识士恰好认识r 个女士，每个女士也恰好认识个女士，每个女士也恰好认识r 个男士。个男士。问问：在这个团中，能否做到：每个男士与其认识的女士：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。跳舞，每个女士也与其认识的男士跳舞。比如：任意比如：任意6个人，一定有个人，一定有3个人相个人相互认识或者有互认识或者有3个人相互不认识个人相互不认识 鸽笼原理和鸽笼原理和鸽笼原理和鸽笼原理和RamseyRamsey数数数数图图的的基基本本概概念念与与模模型型China University of Mining and Technology-9-运筹学 四色猜想四色猜想四
8、色猜想四色猜想 能否用四种颜色给地图染色，能否用四种颜色给地图染色，使相邻的国家有不同的颜色。使相邻的国家有不同的颜色。问题问题：能否用四种颜色给平面能否用四种颜色给平面图的点染色，使有公共边的点有图的点染色，使有公共边的点有不同的颜色。不同的颜色。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-10-运筹学Mbius在在1840年的一次演讲中提出如下问题：一个国王有五年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各
9、自的宫殿。要求每座宫殿之间都有（平面的）路相连并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为研究后指出这是不可能的。因为5个顶点的完全图不个顶点的完全图不是是平面图平面图。平面图在印刷电路板中有重要的应用。平面图在印刷电路板中有重要的应用。平面图与网络平面图与网络平面图与网络平面图与网络图图的的基基本本概概念念与与模模型型China University of Mining and Technology-11-运筹学n-方体方体Qnn n方体方体方体方体n 维立方体维立方体n=3的情形，
10、上底下底是两个的情形，上底下底是两个2维立方体。对应顶点连线后维立方体。对应顶点连线后(同同时把上底中顶点标号末位加号时把上底中顶点标号末位加号0，下底中顶点标号末位加号，下底中顶点标号末位加号1)得到得到3维立方维立方体。体。China University of Mining and Technology-12-运筹学次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数
11、次为偶数的点称作的点称作偶点偶点，次为次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-13-运筹学链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1
12、e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-14-运筹学二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5
13、v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-15-运筹学完全二分图完全二分图是具有二分划是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个顶的每个顶点与点与Y的每个顶点都相连。完全二分图记为的每个顶点都相连。完全二分图记为Km,nK3,3K2,4China University of Mining and Techno
14、logy-16-运筹学G2G1G2G1China University of Mining and Technology-17-运筹学G2G1China University of Mining and Technology-18-运筹学网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权，赋予权的图，赋予权的图G称为网络称为网络(或或赋权图赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为
15、无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256图图的的基基本本概概念念与与模模型型China University of Mining and Technology-19-运筹学出次与入次出次与入次有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi)；vi 点的出次和入次之和就是该点的次。点的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之和。有向图中，所有顶点的
16、入次之和等于所有顶点的出次之和。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-20-运筹学uu一个图是二部图当且仅当它不含奇圈。一个图是二部图当且仅当它不含奇圈。一个图是二部图当且仅当它不含奇圈。一个图是二部图当且仅当它不含奇圈。u设设G是一个简单图，若是一个简单图，若(G)2，则，则G中必含有圈。中必含有圈。u设设G是简单图，若是简单图，若(G)3,则则G必有偶圈。必有偶圈。u设有设有2n 个电话交换台，每个台与至少个电话交换台，每个台与至少n 个台有直通线路，则个台有直通线路，则该交换系统中任二台均可实现通话。该交换
17、系统中任二台均可实现通话。回答：回答：China University of Mining and Technology-21-运筹学图的基本性质：图的基本性质：图的基本性质：图的基本性质：定理定理1任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的条边均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V
18、2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的次之和也为偶数，所以也为偶数，所以必必为偶数，即奇数点的个数必为偶数。为偶数，即奇数点的个数必为偶数。图图的的基基本本概概念念与与模模型型China University of Mining and Technology-22-运筹学图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所
19、关心的问题不同而有：阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等邻接矩阵、关联矩阵、权矩阵等1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方矩阵阶方矩阵A=(aij)n n，其中，其中图图的的基基本本概概念念与与模模型型China University of Mining and Technology-23-运筹学2.2.关联矩阵关联矩阵关联矩阵关联矩阵对于图对于图G=(V,E),|V|=n,|E|=m,有有m n阶矩阵阶矩阵M=(mij)m n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵对于赋权图对于赋权图G=(V,E),其中边其
20、中边有权有权,构造矩阵构造矩阵B=(bij)n n其中：其中：图图的的基基本本概概念念与与模模型型China University of Mining and Technology-24-运筹学v5v1v2v3v4v64332256437下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下图图的的基基本本概概念念与与模模型型例例1China University of Mining and Technology-25-运筹学v1v2v3v4v5v6v7v8v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4下图所表示的图可以构造邻接矩阵下图所
21、表示的图可以构造邻接矩阵M如下如下:M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000图图的的基基本本概概念念与与模模型型例例2China University of Mining and Technology-26-运筹学v5v1v2v3v4v64332256437下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:图图的的基基本本概概念念与与模模型型例例3China University of Mining and T
22、echnology-27-运筹学树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。乒乓求单打比赛抽签后，可用图来表示相遇情况，如下乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。图所示。AB CDEF GH运动员运动员树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-28-运筹学某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。树树 与与 图图 的的 最最 小小 树树厂长厂长人人事事科科财财务务科科总总工工程程
23、师师生生产产副副厂厂长长经经营营副副厂厂长长技技术术科科新新产产品品开开发发科科生生产产科科设设备备科科供供应应科科动动力力科科检检验验科科销销售售科科China University of Mining and Technology-29-运筹学树树是一个不包含圈的简单连通图。是一个不包含圈的简单连通图。树中度为树中度为1的点称为的点称为树叶树叶，度大于，度大于1的点称为的点称为分枝点分枝点。具有具有k个连通分支的不包含圈的图称为个连通分支的不包含圈的图称为k-树，或树，或森林森林。下是具有六个顶点的树下是具有六个顶点的树，图中的每棵树都只有图中的每棵树都只有5条边，并且至少条边，并且至少有
24、有2个顶点的次数是个顶点的次数是1。China University of Mining and Technology-30-运筹学树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为任何树中必存在次为1的点。的点。性质性质2：n个顶点的树必有个顶点的树必有n-1条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v
25、1v2v3v4v5v6树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-31-运筹学图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树（或的部分树（或支撑树）。支撑树）。树图的各条边称为树枝。树图的各条边称为树枝。一般图一般图G1含有多个部分树，其中树枝总长最小的部分树，称含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2树树
26、与与 图图 的的 最最 小小 树树China University of Mining and Technology-32-运筹学(赋权赋权)图中求最小树的方法：破圈法和避圈法图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-33-运筹学v1v2v3v4v5v643521得到最小树：得到最小树：MinC(T
27、)=15树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-34-运筹学避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-35-运筹学v1v2v3v4v5
28、v6435215v1v2v3v4v5v6843752618MinC(T)=15树树 与与 图图 的的 最最 小小 树树China University of Mining and Technology-36-运筹学10.3 最短路问题China University of Mining and Technology-37-运筹学如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边
29、之和（如然是二边之和（如ABAC）。）。ABC最最 短短 路路 问问 题题China University of Mining and Technology-38-运筹学ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长比原来只连三点的最短。最短新路径之长比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。性也更好。最最 短短 路路 问问 题题China University of Mining and Techno
30、logy-39-运筹学问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。最最 短短 路路 问问 题题China University of Mining and Technology-40-运筹学渡河游
31、戏渡河游戏渡河游戏渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法并且在河上来回次数最少？这个问题就可以用求最短路方法解决。解决。最最 短短 路路 问问 题题例例1China Un
32、iversity of Mining and Technology-41-运筹学定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点vi表示河岸的状态表示河岸的状态3）边边ek表示由状态表示由状态vi经一次渡河到状态经一次渡河到状态vj4）权权边边ek上的权定为上的权定为1我们可以得到下面的加权有向图我们可以得到下面的加权有向图最最 短短 路路 问问 题题China University of Mining and Technology-42-运筹学状态说明：状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,
33、u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从v1到到u1的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1最最 短短 路路 问问 题题China University of Mining and Technology-43-运筹学求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法逐次逼近算法逐次逼近算法最最 短短 路路 问问 题题China University of Mining and Technology-44-运筹学狄克斯屈拉狄克斯屈
34、拉狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：若序列若序列vs，v1.vn-1，vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列vs，v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2v3v4是是v1v4的最短路，则的最短路，则v1v2v3一定是一定是v1v3的最短路，的最短路，v2v3v4也一定是也一定是v2v4的最短路。的最短路。v1v2v3v4v5最最 短短 路路 问问 题题China University of Mining and Techno
35、logy-45-运筹学DijkstraDijkstra算法算法算法算法基本步骤基本步骤基本步骤基本步骤Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步地向外探寻最出发，逐步地向外探寻最短路，采用短路，采用标号法标号法。执行过程中，与每个点对应，记录下一个数（称为这个执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从点的标号），它或者表示从vs到该点的最短路长（称为到该点的最短路长（称为P标标号号），或者是从），或者是从vs到该点的最短路长的上界（称为到该点的最短路长的上界（称为T标号标号）。）。算法每一步都把某个顶点的算法每一步都把某个顶点的T 标号改为
36、标号改为P 标号，标号，当终点当终点vt得到得到P 标号时，计算结束。最多标号时，计算结束。最多n-1步。步。最最 短短 路路 问问 题题China University of Mining and Technology-46-运筹学网络图的最短路网络图的最短路图的起点是图的起点是vs，终点是，终点是vt ，以，以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j)，距离为距离为dij。P P标号标号标号标号(点标号点标号点标号点标号)：b(j)起点起点vs到点到点vj的最短路长；的最短路长；T T标号标号标号标号(边标号边标号边标号边标号)：k(i,j)=b(i)+dij。最最 短短
37、路路 问问 题题China University of Mining and Technology-47-运筹学步骤：步骤：2.找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合B=(i,j)如果这样的如果这样的弧不存在或弧不存在或vt已标号则计算结束；已标号则计算结束；3.计算集合计算集合B中弧中弧k(i，j)=b(i)+dij的标号的标号;4.选一个点标号选一个点标号在终点在终点vl处标号处标号b(l),返回到第返回到第2步。步。1.令起点的标号；令起点的标号；b(s)0。最最 短短 路路 问问 题题China University of Mining and Technol
38、ogy-48-运筹学求连接求连接vs、vt的最短路的最短路.0-P T-开始，给开始，给vs以以P标号，标号，P(vs)=0,其余各点给其余各点给T 标号标号T(vi)=+.227414731555vsv2v1vtv4v5v3Step1:迭迭代代1DijkstraDijkstra算法基本步骤：算法基本步骤：算法基本步骤：算法基本步骤：例例2最最 短短 路路 问问 题题China University of Mining and Technology-49-运筹学0-若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。22741
39、4731555vsv2v1vtv4v5v3Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij245迭迭代代1考察考察vs,T(v2)=minT(v2),P(vs)+ws2=min+,0+5=5T(v1)=minT(v1),P(vs)+ws1=min+,0+2=2最最 短短 路路 问问 题题China University of Mining and Technology-50-运筹学0-比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，227414731555vsv2v1vtv4v5v3Step3:2
40、45即即 P(vi)=minT(vi).当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P 标号。若全部点为标号。若全部点为P标号标号,则停止。否则用则停止。否则用vi代替代替vi转转step2.-2迭迭代代1全部全部T标号中标号中,T(v1)最小最小,令令P(v1)=2,记录路径记录路径(vs,v1).最最 短短 路路 问问 题题China University of Mining and Technology-51-运筹学0-2-5-4227414731555vsv2v1vtv4v5v394若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi
41、,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij迭迭代代2考察考察v1,T(v4)=minT(v4),P(v1)+w14=min+,2+7=9T(v2)=minT(v2),P(v1)+w12=min5,2+2=4最最 短短 路路 问问 题题China University of Mining and Technology-52-运筹学0-2-4-9-4227414731555vsv2v1vtv4v5v344迭迭代代2比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标
42、号，Step3:即即 P(vi)=minT(vi).-全部全部T 标号中标号中,T(v2),T(v3)最小最小,令令P(v2)=4,P(v3)=4,记录路径记录路径(v1,v2),(v1,v4),.最最 短短 路路 问问 题题China University of Mining and Technology-53-运筹学0-2-4-9-4-227414731555vsv2v1vtv4v5v37迭迭代代3若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=m
43、inT(vj),P(vi)+wij最最 短短 路路 问问 题题China University of Mining and Technology-54-运筹学0-2-4-9-74-227414731555vsv2v1vtv4v5v37迭迭代代3比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).-最最 短短 路路 问问 题题China University of Mining and Technology-55-运筹学0-2-4-9-7-4-227414731555vsv2v1vtv4v5v3迭迭代代4若若vi
44、为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij814最最 短短 路路 问问 题题China University of Mining and Technology-56-运筹学0-2-4-8-147-4-227414731555vsv2v1vtv4v5v3迭迭代代48-比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).最最 短短 路路 问问
45、题题China University of Mining and Technology-57-运筹学0-2-4-8-147-4-227414731555vsv2v1vtv4v5v3迭迭代代513若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij最最 短短 路路 问问 题题China University of Mining and Technology-58-运筹学0-2-4-8-137-4-227414731555v
46、sv2v1vtv4v5v3迭迭代代513比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P 标号。若全部点为标号。若全部点为P标号标号,则停止。否则用则停止。否则用vi代替代替vi转转step2.-最最 短短 路路 问问 题题China University of Mining and Technology-59-运筹学0-2-4-8-13-7-4-227414731555vsv2v1vtv4v5v3最短路最短路Dijkstra算法不仅找到了所
47、求最短路，而且找到了从算法不仅找到了所求最短路，而且找到了从vs点点到其他所有顶点的最短路；这些最短路构成了图的一个到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。连通无圈的支撑子图，即图的一个支撑树。最最 短短 路路 问问 题题China University of Mining and Technology-60-运筹学从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的
48、最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj。最最 短短 路路 问问 题题China University of Mining and Technology-61-运筹学算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近边上权为负的，算法失效。此时可采用逐次逼近算法。算法。如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv1的最短的最短路长显然是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-
49、58最最 短短 路路 问问 题题例例2China University of Mining and Technology-62-运筹学Ford算法基本思想：算法基本思想：为逐次逼近的方法。每次求出从出发点为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找即第一次逼近是找v0到到vn的最短路，但限于最短路只允许有的最短路，但限于最短路只允许有一条边（弧），其距离记为一条边（弧），其距离记为d1(v0,vn).简记为简记为d 1(vn)。第二次逼近，再找第二次逼近，再找v0到到vn的最短路，其限制条件放宽到允许的最
50、短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为最短路不超过两条边（弧），其距离记为d 2(vn)。到第到第m次逼近次逼近,d m(vn)表示由表示由v0到到vn的不超过的不超过m条边（弧）组条边（弧）组成的最短路的距离。最多成的最短路的距离。最多p-1次。次。网络有负权的最短路网络有负权的最短路网络有负权的最短路网络有负权的最短路最最 短短 路路 问问 题题China University of Mining and Technology-63-运筹学2-2-2311v0v2v1v3FordFord算法基本步骤：算法基本步骤：算法基本步骤：算法基本步骤：(1)令令m=1,令令d