我的OI心得(四)之图论(三).doc_第1页
我的OI心得(四)之图论(三).doc_第2页
我的OI心得(四)之图论(三).doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

单源最短路径重点课题！单源最短路径（SSSP）是这样一个问题：在一张图中，有一个源点S，点与点之间有边，边上有权值，表示从边的这头走到边的那头要付出的代价（距离）。求点S到其余所有点的最小距离。书上讲了Dijkstra。朴素Dijkstra呢，NOIP一般就是小数据用用，O(n2)敷衍了事（如果你觉得用着顺的话）；对付大数据也不是不行，但是得加个堆（相关章节自行查阅），用于维护和查询当前的距离最小的点再加上邻接表或边集数组，复杂度降为O(nlgn+e)，不过编程复杂度较高，不赞成使用。但是Dijkstra的思路还是要搞懂的就是说我每次都选“还没确定的”到源点距离最小的点i，他当前的到S的距离di一定可以确定是i到S的最短距离：没有比他更小的没更新过他的点了。把这个点选出来（可以用堆）后，用他更新与他直接相连的若干点，跟他们说：哥们，走我这试试看，能不能更近点。然后西去修成正果i也变成了“已确定的点”。做n-1个点后（ds=0），算法结束。然而我要说的是我们可以用宽搜做！状态就是当前点的编号！加上上面的数组d，这个叫SPFA的算法效果非常好！注意在Dijkstra中有个Relax操作：设i-j的边权为ci,j，则我们可以做如下操作：if djdi+ci,j then dj=di+ci,j;。这步操作很关键。如果上述语句成功执行，那么无疑dj将变小，那么所有j连出去的点的d值也有可能变小，应此我们应当挨个访问一下。不急，我们学学人家宽搜，用个队列，把j扔队尾去(如果j不在队列的话)。流程如下：procedure SPFA(s:integer);varn,v,u,t1,t2:integer;d:array1.1000of integer;c:array1.1000,1.1000of integer;queue:array1.1000of intger;begint1=1;t2=1;q1=s;repeatu=qt1;inc(t1);flagu=false;for v:=1 to n doif (cu,v0) and (dvdu+cu,v) thenbegindv:=du+cu,v;if not flagv thenbegininc(t2);qt2:=v;flagv:=true;end;end;until t1=t2;end;事实上，SPFA是NOIP中最常用的单源最短路径算法也就是宽搜+判重（d数组和flag数组）
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论