




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1
第十九讲最短路径12教材与参考资料普通高等教育“十一五”国家级规划教材普通高等教育精品教材《算法与数据结构—C语言描述》(第2版)张乃孝编著,高等教育出版社2008.第9章图(9.5)普通高等教育“十一五”国家级规划教材配套参考书《算法与数据结构》(第2版)学习指导与习题解析张乃孝编著,高等教育出版社2009.239.5最短路径如果图中从一个顶点可以到达另一个顶点,则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径,而每条路径上经过的边数并不一定相同。如果图是一个带权图,则路径长度为路径上各边的权值的总和,两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径,其路径长度称为最短路径长度。49.5.1Dijkstra算法Dijkstra算法求解从顶点v0出发到其它各顶点最短路径。该算法假设所有边的权都大于等于零。5基本思想设置一个集合U,存放已求出最短路径的顶点,V-U是尚未确定最短路径的顶点集合。U的初始状态为{v0}。按路径长度递增的次序逐个产生vx的最短路径,把vx加入U中。直到U=V时终止。距离值V-U图GUv0vi1vi3vi2为每个顶点设置一个距离值(已知最短距离):集合U中某顶点的距离值就是从顶点v0到该顶点的最短路径长度;集合V-U中某顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。性质:若vi是V-U中距离值最小的结点,那么这个距离值就是从v0到vi的最短路径。。67初始状态:集合U中只有顶点v0,顶点v0对应的距离值为0,集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权,如果v0和vi间无边直接相连,则vi的距离值为∞(实际程序中可以用一个足够大的数代替)。处理框架:(1)在集合V-U中选择距离值最小的顶点vmin加入集合U;(2)对集合V-U中各顶点的距离值进行修正:如果加入顶点vmin为中间顶点后,使v0到vi的距离值比原来的距离值更小,则修改vi的距离值。(3)重复(1)(2)操作,直到从v0出发可以到达的所有顶点都在集合U中为止。按路径长度递增的次序逐个产生最短路径例:已知带权图G10如下图所示及其邻接矩阵A,求从顶点v0到其它各顶点的最短路径úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥=03030350201502051504510500A45v050v15v41520v215v33v53520301045v050v15v41520v215v33v535203010[45][50][10][¥][¥]绿色为从U到V-U的边,选(v0,v2)把v2加入U845v050v15v41520v215v33v535203010[¥][45][25][50]选(v2,v3),把v3加入U45v050v15v41520v215v33v535203010[45][45][¥]选(v3,v1),把v1加入U45v050v15v41520v215v33v535203010[¥][45]选(v0,v4),把v4加入U45v050v15v41520v215v33v535203010910图选择邻接矩阵表示法,其中关系矩阵的对角线初值均取0。算法中,将放入集合U中结点对应的关系矩阵中对角线元素值修改为1;另外设置一个数组dist,dist[i]用于存放v0到顶点vi的最短路径及其最短路径长度(计算过程中为距离值)∶
ypedefstruct{ AdjTypelength; /*最短路径长度*/ intprevex; /*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Path*dist;存储结构11修正距离值方法的精化在加入顶点vmin为中间顶点后,如果dist[i].length>dist[min].length+G.arcs[min][i],则将顶点vi的距离值改为:dist[min].length+G.arcs[min][i]并修改路径上vi的前趋顶点:dist[i].prevex=min。
12①.初始时,集合U中只有顶点v0。结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}②.在集合V-U中找出距离值最小的顶点v2,将顶点v2加入集合U中。结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}③.按min=2调整集合V-U中顶点的距离值。因为dist[1].legth=50,dist[2].length+graph.arcs[2][1]=10+MAX,因此,顶点v1的距离值不需要调整。因为dist[3].length=MAX,dist[2].length+graph.arcs[2][3]=10+15=25,因此,顶点v3的距离值调整为25,其前趋顶点为v2。同理,顶点v4,v5的距离值不需要调整。结果dist[n]为{{0,0},{50,0},{10,0},{25,2},{45,0},{MAX,-1}}在数组dist上模拟算法13④.同理在集合V-U中找出当前距离值最小的顶点v3,并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑤.在集合V-U中找出当前距离值最小的顶点v1。并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},
{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑥.在集合V-U中找出当前距离值最小的顶点v4。并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑦.没有可以再加入集合U的顶点了,说明从顶点v0到顶点v5之间无路径相通。过程结束。在数组dist上模拟算法(续)14
由数组dist的prevex字段得到顶点v0到各顶点的最短路径{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}如从v0到v1的最短路径,dist[1].prevex=3可知路径上顶点v1的前一个顶点是v3,dist[3].prevex=2可知路径上顶点v3的前一个顶点是v2,dist[2].prevex=0可知路径上前一个顶点是v0,即最短路径为(v0,v2,v3,v1)。voidinit(GraphMatrix*pgraph,Pathdist[]){inti;dist[0].length=0;dist[0].prevex=0;pgraph->arcs[0][0]=1;/*用矩阵对角线元素记录集合U,为1表示在U中。*/for(i=1;i<pgraph->n;++i){/*初始化V-U中顶点的距离值*/
dist[i].length=pgraph->arcs[0][i];if(dist[i].length!=MAX)dist[i].prevex=0;elsedist[i].prevex=-1;}}15初始化dist[]voiddijkstra(GraphMatrix*graph,Pathdist[]){inti,j,mv,n=graph->n;AdjTypeminw;init(graph,dist);/*初始化,集合U中只有顶点v0*/for(i=1;i<n;++i){minw=MAX;mv=0;
for(j=1;j<n;++j)/*在V-U中选出距v0最近的顶点*/if(graph->arcs[j][j]==0&&dist[j].length<minw){mv=j;minw=dist[j].len;}if(mv==0)break;/*v0与V-U的顶点不连通,结束*/graph->arcs[mv][mv]=1;/*顶点mv加入U*/for(j=1;j<n;++j){/*调整V-U顶点的已知最短路径*/if(graph->arcs[j][j]==0&&/*为V-U的顶点*/dist[j].length>dist[mv].length+graph->arcs[mv][j]){dist[j].prevex=mv;/*调整已知最短路径信息*/dist[j].length=dist[mv].length+graph->arcs[mv][j];}}}}16Dijkstra算法17算法分析算法中的初始化部分的时间复杂度为O(n),求最短路径部分由一个大循环组成,其中外循环运行n-1次,内循环为两个,均运行n-1次,因此,算法的时间复杂度为O(n2)。另外需要注意,在算法中改变了关系矩阵中的初始状态,如果要求算法不能破坏原始数据,就需要另外增加数据结构记录U集合的值。空间代价是O(n).189.5.2Floyd算法功能:求带权图每一对顶点间的最短路径基本思想:图采用邻接矩阵作为存储结构。把关系矩阵看成是没有经过任何中间结点,直接可以到达的每一对顶点间的最短路径。然后按结点在结点表中的顺序,每次考虑增加一个新的结点,在允许这个结点作为中间结点的条件下,计算每一对顶点间的最短路径的缩短变化。直到把所有结点都考虑进去为止,结果得到每一对顶点间的最短路径。19数据结构
为了在算法中不破坏原始的关系矩阵,需要定义一个与关系矩阵同样大小,以关系矩阵作为其初始状态的矩阵,用于存放处理中每对顶点间的距离值(或最短路径长度)。为了保存全部最短路径的轨迹,需要另外设计一个与关系矩阵同样大小的整数矩阵,存放vi到vj最短路径上vi的后继顶点的下标值。把它们封装在下面定义的结构类型ShortPath中:
typedefstruct{ AdjType*a[];/*存放每对顶点间最短路径长度*/ int*nextvex[];/*存放vi到vj最短路径上vi的后继顶点的下标值*/}ShortPath;voidFloyd(GraphMatrix*pgraph,ShortPath*ppath){inti,j,k,n=pgraph->n;for(i=0;i<n;++i)for(j=0;j<n;++j){if(pgraph->arcs[i][j]!=MAX)ppath->nextvex[i][j]=j;elseppath->nextvex[i][j]=-1;ppath->a[i][j]=pgraph->arcs[i][j];/*复制邻接矩阵*/}for(k=0;k<n;++k)for(i=0;i<n;++i)for(j=0;j<n;++j){if(ppath->a[i][k]==MAX||ppath->a[k][j]==MAX)continue;if(ppath->a[i][j]>ppath->a[i][k]+ppath->a[k][j]){ppath->a[i][j]=ppath->a[i][k]+ppath->a[k][j];ppath->nextvex[i][j]=ppath->nextvex[i][k];}
}}20Floyd算法21代价分析算法中初始化部分由一个两重循环组成,其中外循环运行n次,内循环也运行n次,初始化部分的时间复杂度为O(n2)。迭代生成最短路径长度矩阵A和路径矩阵nextvex的部分为三重循环的嵌套,其时间复杂度为O(n3)。Floyd算法的时间复杂度为O(n3)。
空间代价是O(n2)(比较大)。22例题用Floyd方法求图G10各顶点间的最短路径长度。23初始状态24加入V025加入V126加入V227加入V328例如,想知道v0到v1的最短路径:由A[0][1]可知v0到v1的最短路径长度为45,路径由nextvex[0][1]=2可知顶点v0的下一顶点为v2,由nextvex[2][1]=3可知v2的下一顶点为v3,由nextvex[3][1]=1可知v3的下一顶点为v1,因此从v0到v1的最短路径为v0→v2→v3→v1路径的查找29本讲重点:图中从一个顶点到另一个顶点间路径长度最短的路径称为两个顶点间的最短路径。本章介绍了从顶点v0出发到其它顶点最短路径的Dijkstra算法和求每一对顶点间的最短路径的Floyd算法。讨论:动态规划算法*有些问题在分解时会产生大量的子问题,同时分得的子问题界限不清,互相交叉,因而在解这类问题时,将可能重复多次解同一个子问题。解决的方法可以在解决每个子问题后把它的解(包括其子子问题的解)保留在一个表格中,若遇到求与之相同的子问题的解时,就可以从表中把解找出来直接使用。本书所见过的运用动态规划法的算法有:所有结点间的最短路径算法(算法9.7)及最佳二叉排序树的构造算法(算法7.5)。30给定排序的关键码集合{key1,key2,…,keyn}和两个权集合{p1,…,pn}和{q0,q1…,qn},其中pi是检索内部结点i的概率,
qj是被检索关键码属于外部结点j的关键码集合的概率.问题
:要求构造一棵最佳二叉排序树,即构造出一棵二叉排序树,使下面的函数达到最小(E(n)一定也达到最小):上式称为包含n个内部结点和n+1个外部结点的二叉排序树的花费,记作C(0,n).性质:最佳二叉排序树里的任何子树都最佳.31回顾:不等概率的最佳二叉排序树的构造花费的计算在构造T(i,j)时,对所有i<k≤j,
T(i,k-1)和T(k,j)都已存在,而且已知相应花费C(i,k)和C(k,j).对每个k,以keyk
为根,
T(i,k-1)和T(k,j)为左右子树的二叉树的花费为:
Ck(i,j)=W(i,j)+C(i,k-1)+C(k,j)
(结点增加一层).从所有可能k中选择使Ck(i,j)达到最小的那个k,与之对应树就是T(i,j),其根R(i,j)=k.新树的代价可以由构造它的已知最佳二叉排序树的代价算出:C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).NOTE:T(i,i)为不包含任何内部结点,仅仅由权值为qi的外部结点构成,C(i,i)=0.32数组p存放内部结点的权(p[1],…,p[n]);数组q存放外部结点的权(q[0],…,q[n]);c[i][j]保存T(i,j)的花费;w[i][j]保存T(i,j)的权;r[i][j]保存T(i,j)的根.构造好的最佳二叉排序树的总花费存放在c[0][n];r[0][n]是根结点的编号。根据r[0][n]的值,就可以确定两棵子二叉树的根在那里:33数据的存储w: 4121417 0358 0014 0001直接算出r: 0100 0020 0003 0000c: 01200 0050 0004 0000第一步r: 0110 0022 0003 0000c: 012190 00512 0004 0000第二步r: 0111 0022 0003 0000c: 0121929 00512 0004 0000第三步计算结果:34P:{5,1,2}Q:{4,3,1,1}C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).
1,求着色问题近似解的贪心法。
2,构造最小生成树的prim算法(算法9.5)。这里的条件是所有权都是正数,在遇到带有负权边的图时,这样做就可能产生错误的结果。
3,Dijkstra的最短路径算法(算法9.6)求从源点到其他各结点的最短路径。这里的条件是所有权都是正数,在遇到带有负权边的图时,这样做就可能产生错误的结果。
35贪心法动态规划法与贪心法的相同点两者的相同点是
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高性能回弹泡棉项目投资可行性研究分析报告(2024-2030版)
- 2025年中国岩盐灯行业市场发展前景及发展趋势与投资战略研究报告
- 2025-2030年中国茶油市场运营状况与发展趋势前景展望研究报告
- 2025-2030年中国泵风机喷灌机械项目投资可行性研究分析报告
- 五岁以下儿童死亡监测死因诊断分类
- 12.3 课时2 分式的混合运算 能力提升精练
- 改建项目节能评估报告
- 平面升降板项目可行性研究报告申请报告
- 甜酸荠头咸荠头行业深度研究分析报告(2024-2030版)
- 中国气源式喷码机行业市场发展前景及发展趋势与投资战略研究报告(2024-2030)
- 迪庆藏族自治州发电有限责任公司新乐水电站环境影响后评价报告书
- 《中药学》课件-中药思政元素案例
- 高压水除磷系统在柳钢热轧生产线上的使用和创新
- 医院保洁服务投标方案(完整技术标)
- 广东省深圳市宝安区2022-2023学年二年级下学期期末数学试卷
- 幼儿园规范化幼儿园参评自评报告
- 光伏发电售后合同范本
- 《水资源管理》机考题库及答案开放大学考试题库 答案
- 菜鸟WMS(大宝)操作手册 (修复的)
- 东南亚艺术概论智慧树知到答案章节测试2023年云南艺术学院
- 卫生经济学智慧树知到答案章节测试2023年华中科技大学
评论
0/150
提交评论