数学最短路问题学习教案

1、数学最短路数学最短路(dunl)问题问题第一页，共36页。第1页/共35页第二页，共36页。第2页/共35页第三页，共36页。第3页/共35页第四页，共36页。问题归结为：从任一点出发一笔画(bhu)出七条线再回到起点 问题：要从这四块陆地中的任何一块开始通过每一座 桥正好一次，再回到起点。一笔画的一个判定法则：这个图是连通的，且每个点都 与偶数线相关联 第4页/共35页第五页，共36页。基本(jbn)问题： 匹配(ppi)问题 最小费用流问题 最大流问题 最短路问题第5页/共35页第六页，共36页。从甲地到乙地的公路网纵横交错，因此(ync)有多种 行车路线，这名司机应选择哪条线路呢？假设货

2、柜车的运行速度是恒定的，那么这一问 题相当于需要找到一条从甲地到乙地的最短路。 第6页/共35页第七页，共36页。 假定已经知道了任意两个城市之间修建高速公路的成本(chngbn)，那么应如何决定在哪些城市间修建高速公路，使得总成本(chngbn)最小？第7页/共35页第八页，共36页。 如何分配(fnpi)工作方案可以使总回报最大？第8页/共35页第九页，共36页。如何(rh)为他（她）设计一条最短的投递路线 （从邮局出发，经过投递区内每条街道至少 一次，最后返回邮局）？ 管梅谷教授 1960年首先提出的 第9页/共35页第十页，共36页。如何为他（她）设计一条最短的旅行路线 （从驻地出发，

3、经过(jnggu)每个城市恰好一次， 最后返回驻地）？ 第10页/共35页第十一页，共36页。 那么如何安排(npi)运输方案可以使总运输成本 最低？ 第11页/共35页第十二页，共36页。 2、易于用图形的形式直观地描述和表达，数学 上把这种与图相关的结构(jigu)称为网络(network)。 与图和网络相关的最优化问题就是网络最优化或 称网络优化 （netwok optimization）问题。第12页/共35页第十三页，共36页。第13页/共35页第十四页，共36页。最短路最短路(dunl)问题问题基本基本(jbn)内容内容2、会用、会用Matlab软件软件(run jin)求最短求最

4、短路路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图 论 的 基 本 概 念2、最 短 路 问 题 及 其 算 法3、最 短 路 的 应 用4、建模案例：最优截断切割问题5、实验作业第14页/共35页第十五页，共36页。图 论 的 基 本 概 念一、 图 的 概 念1、图的定义(dngy)2、顶点(dngdin)的次数 3、子图二、 图 的 矩 阵 表 示1、 关联矩阵2、 邻接矩阵返回(fnhu)第15页/共35页第十六页，共36页。定义有序三元组G=(V,E, )称为一个图.1 V=,21nvvv是有穷非空集，称为顶顶点点集集， 其中的元素叫图 G 的顶顶点点.2 E 称为边

5、边集集，其中的元素叫图 G 的边边.3 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关关联联函函数数.例例1 设 G=(V ,E,)，其中 V=v1 ,v2 , v3 , v4， E=e1, e2 , e3, e4, e5,335414413312211)(,)(,)(,)(,)(vvevvevvevvevve.G 的图解如图.图的定义(dngy)第16页/共35页第十七页，共36页。定义在图 G 中，与 V 中的有序偶(vi， vj)对应的边 e，称为图的有有向向边边（或弧） ，而与 V 中顶点的无序偶 vivj相对应的边 e，称为图的无无向向边边.每一条边都是无

6、向边的图，叫无无向向图图；每一条边都是有向边的图，称为有有向向图图；既有无向边又有有向边的图称为混混合合图图.定义若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权权，并称图 G 为赋赋权权图图.规定用记号和分别表示图的顶点数和边数.第17页/共35页第十八页，共36页。常用术语：（） 端点相同的边称为环环（） 若一对顶点之间有两条以上的边联结，则这些边称为重边重边（） 有边联结的两个顶点称为相邻的顶点相邻的顶点，有一个公共端点的边 称为相邻的边相邻的边（） 边和它的端点称为互相关联关联的 （） 既没有环也没有平行边的图，称为简单图简单图（） 任意两顶点都相邻的简单图，

7、称为完备图完备图，记为 Kn，其中 n 为顶点的数目( 7)若 V=XY，XY=，X 中任两顶点不相邻，Y 中任两顶点不相邻，称 G 为二元图二元图；若 X 中每一顶点皆与 Y 中一切顶点相邻，称为完备二元图完备二元图，记为 Km,n，其中 m,n 分别为 X 与 Y 的顶点数目第18页/共35页第十九页，共36页。第19页/共35页第二十页，共36页。顶点(dngdin)的次数定定义义（）在无向图中，与顶点 v 关联的边的数目（环算两次）称为 v的次次数数，记为 d(v)（）在有向图中，从顶点 v 引出的边的数目称为 v的出出度度，记为 d+(v)，从顶点 v引入的边的数目称为的入入度度，记

8、为 d-(v)，d(v)=d+(v)+d-(v)称为 v的次数4)(4vd5)(3)(2)(444vdvdvd4)(4vd第20页/共35页第二十一页，共36页。定理定理)(2)()(GvdGVv推论推论任何图中奇次顶点的总数必为偶数例 在一次聚会(jhu)中，认识奇数个人的人数一定是偶数。第21页/共35页第二十二页，共36页。子图(1) 若 V1V，E1E,且当 eE1时，1(e)= (e),则称 G1是 G 的子子图图特别的，若 V1=V，则 G1称为 G 的生生成成子子图图(2) 设 V1V，且 V1，以 V1为顶点集、两个端点都在 V1中的图 G 的边为边集的图 G 的子图，称为 G

9、 的由由 V1导导出出的的子子图图，记为 GV1.(3)设 E1E,且 E1,以 E1为边集,E1的端点集为顶点集的图 G 的子图,称为 G 的由由 E1导导出出的的子子图图,记为 GE1. GGv1,v4,v5Ge1,e2,e3第22页/共35页第二十三页，共36页。关联矩阵对无向图，其关联矩阵)(ijm，其中：不关联与若相关联与若jijiijevevm01M=43215432110110011000101110001vvvveeeee对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设(jish)图为简单图返回(fnhu)第23页

10、/共35页第二十四页，共36页。邻接矩阵对无向图，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设(jish)图为简单图A=432143210111101011011010vvvvvvvv对有向图（，） ，其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01第24页/共35页第二十五页，共36页。对有向赋权图，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义A=4321432105375083802720vvvvvvvv返回(fnhu)第25页/共35页

11、第二十六页，共36页。最 短 路 问 题 及 其 算 法一、 基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回(fnhu)第26页/共35页第二十七页，共36页。基 本 概 念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定义定义在无向图 G=(V,E,)中：（） 顶点与边相互交错且iiivve1)( (i=1,2,k)的有限非空序列)(12110kkkvevevevw称为一条从0v到kv的通路通路，记为kvvW0（）边不重复但顶点可重复的通路称为道路道

12、路，记为kvvT0（）边与顶点均不重复的通路称为路径路径，记为kvvP0第27页/共35页第二十八页，共36页。定义定义（）任意两点均有路径的图称为连通图连通图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树定定义义（）设 P(u,v)是赋权图 G 中从 u 到 v的路径， 则称)()()(PEeewPw为路径 P 的权权(2) 在赋权图 G 中，从顶点 u 到顶点 v的具有最小权的路 ),(*vuP，称为 u 到 v的最最短短路路返回(fnhu)第28页/共35页第二十九页，共36页。固 定 起 点 的 最 短 路最短路(dunl)是一条路径，且最短路(dunl)的任一段也是最短路

13、(dunl) 假设(jish)在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程(guchng)来求指定顶点到其余顶点的最短路第29页/共35页第三十页，共36页。Dijkstra 算法算法：求 G 中从顶点 u0到其余顶点的最短路设 G 为赋权有向图或无向图，G 边上的权均非负对每个顶点，定义两个标记（l v( )，z v( )） ，其中: l v( )：表从顶点 u0到 v 的一条路的权 z v( )：v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终l v( )为从顶点u0到 v 的最短路的权S：具有

14、永久标号的顶点集输入: G 的带权邻接矩阵),(vuw第30页/共35页第三十一页，共36页。算法算法(sun f)步骤：步骤：（）赋初值：令 Su0, l u()0=0 vSVS,令l v ( )=W u v(, )0,z v( )=u0 u u0（3） 设v*是使l v( )取最小值的S中的顶点，则令 S=Sv*， uv*（4） 若S ，转 2，否则，停止. 用上述算法求出的l v( )就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0, 就得到u0到v的最短路的路线.（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v( )= u第31页/共35页第三十二页，共36页。例例 求下图从顶点 u1到其余顶点的最短路先写出带权邻接矩阵： 03064093021509701608120W因 G 是无向图，故 W是对称阵 TO MATLAB(road1)第32页/共35页第三十三页，共36页。)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12