还剩18页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
彻底弄懂最短路径问题只想说温故而知新,可以为师矣我大二的《数据结构》是由申老师讲的,那时候不怎么明白,估量太理论化了(PS:或许是由于我睡觉了);今日把老王的2022年课件又看了一遍,给大二的孩子们又讲了一遍,顺手谷歌了N多资料,算是彻底搞懂了最短路径问题请读者尽情享用……我坚信没有不好的同学,只有垃圾的教育不过没有人理所当然的对你好,所以要学会感恩一•问题引入问题从某顶点动身,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径——最短路径解决最短路的问题有以下算法,Dijkstra算法,Bellman-Ford算法Floyd算法和SPFA算法,此外还有闻名的启发式搜寻算法A*不过A*预备单独出一篇,其中Floyd算法可以求解任意两点间的最短路径的长度笔者认为任意一个最短路算法都是基于这样一个事实从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B2是从A经过若干个节点到Bo—.Dijkstra算法该算法在《数据结构》课本里是以贪心的形式讲解的,不过在《运筹学》教材里被编排在动态规划章节,建议读者两篇都看看观看右边表格发觉除最终一个节点外其他均已经求出最短路径USDollar〃我国名BritishPoundFrenchFranc3〃货币兑换数USDollar
0.5BritishPound〃部分货币汇率兑换表BritishPound
10.0FrenchFrancFrenchFranc
0.21USDollar月赛做的题,不过当时用的思路是求强连通重量(PS:明明说的,那时我和华杰感觉好有道理),也没做出来,现在知道了直接floyd算法就ok了思路分析输入的时候可以采纳M叩〈StringInteger〉m叩二newHashMapStringInteger〉()主要是为了获得再次包含汇率输入时候的下标以建图(感觉自己写的好拗口),或者第一次直接存入String数组str再次输入的时候每次遍历str数组,若是equals那么就把str的下标赋值给该币种建图下面就是floyd算法啦,初始化其它点为-1对角线为1采纳乘法更新求最大值H.Bellman-Ford算法为了能够求解边上带有负值的单源最短路径问题,Bellman(贝尔曼,动态规划提出者)和Ford(福特)提出了从源点逐次绕过其他顶点,以缩短到达终点的最短路径长度的方法Bellman-ford算法是求含负权图的单源最短路径算法,效率很低,但代码很简洁写即进行不停地松弛,每次松弛把每条边都更新一下,若n-1次松弛后还能更新,则说明图中有负环,无法得出结果,否则就胜利完成Bellman-ford算法有一个小优化每次松弛先设一个flag初值为FALSE若有边更新则赋值为TRUE最终假如还是FALSE则直接胜利退出Bellman-ford算法铺张了很多时间做无必要的松弛,所以SPFA算法用队列进行了优化,效果非常显著,高效难以想象SPFA还有SLFLLL滚动数组等优化关于SPFA请看我这一篇递推公式(求顶点u到源点v的最短路径):dist1[u]=Edge[v][u]distk[u]=min{distk-1[u]min{distk-1[j]+Edge[j][u]}}j=Ol...n-lj^Dijkstra算法和Bellman算法思想有很大的区分Dijkstra算法在求解过程中源点到集合S内各顶点的最短路径一旦求出,则之后不变了,修改的仅仅是源点到T集合中各顶点的最短路径长度Bellman算法在求解过程中,每次循环都要修改全部顶点的dist[]也就是说源点到各顶点最短路径长度始终要到Bellman算法结束才确定下来算法适用条件.
1.单源最短路径(从源点S到其它全部顶点V)有向图无向图(无向图可以看作(uv)(vu)同属于边集E的有向图)边权可正可负(如有负权回路输出错误提示)差分约束系统(至今貌似只看过一道题)Bellman-Ford算法描述.初始化将除源点外的全部顶点的最短距离估量值d[v]~+8d[s]-
0.迭代求解反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估量值逐步靠近其最短距离;(运行M-i次,看下面的描述性证明(当做树)).检验负权回路推断边集E中的每一条边的两个端点是否收敛假如存在未收敛的顶点,则算法返回false表明问题无解;否则算法返回true并且从源点可达的顶点v的最短距离保存在d[v]中描述性证明(这个解释很好)首先指出,图的任意一条最短路径既不能包含负权回路,也不会包含正权回路,因此它最多包含条边其次,从源点s可达的全部顶点假如存在最短路径,则这些最短路径构成一个以s为根的最短路径树Bellman-Ford算法的迭代松弛操作实际上就是按顶点距离s的层次,逐层生成这棵最短路径树的过程在对每条边进行1遍松弛的时候,生成了从S动身,层次至多为1的那些树枝也就是说,找到了与S至多有1条边相联的那些顶点的最短路径;对每条边进行第2遍松弛的时候,生成了第2层次的树枝,就是说找到了经过2条边相连的那些顶点的最短路径……由于最短路径最多只包含M-i条边,所以,只需要循环|v|-l次每实施一次松弛操作,最短路径树上就会有一层顶点达到其最短距离,此后这层顶点的最短距离值就会始终保持不变,不再受后续松弛操作的影响(但是,每次还要推断松弛,这里铺张了大量的时间,这就是Bellman-Ford算法效率底下的缘由,也正是SPFA优化的所在XC的最短路径不更新,那么点D的最短路径确定也无法更新,这就是优化所在假如没有负权回路,由于最短路径树的高度最多只能是所以最多经过遍松弛操作后,全部从s可达的顶点必将求出最短距离假如d[v]仍保持+8则表明从s到v不行达假如有负权回路,那么第|v|-l遍松弛操作仍旧会胜利,这时,负权回路上的顶点不会收敛参考了《图论》问题Bellman-Ford算法是否肯定要循环n-1次么?未必!其实只要在某次循环过程中,考虑每条边后,都没能转变当前源点到全部顶点的最短路径长度,那么Bellman-Ford算法就可以提前结束了(开篇提出的小优化就是这个)上代码(参考了牛帅的博客)#includeiostream#includecstdiousingnamespacestd;#defineMAXOx3f3f3f3f#defineN1010intnodenumedgenumoriginal;〃点,边z起点typedefstructEdge〃边intuv;intcost;}Edge;Edgeedge[N];intdis[N]zpre[N];boolBellman_Fordforinti=1;i=nodenum;++i〃初始化dis[i]二i二二original0:MAX;forinti=1;i=nodenum-1;++iforintj=!;]=edgenum;++jifdis[edge[j].v]dis[edge[j].u]+edgs[j].cost//松弛挨次肯定不能反~dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;pre[edge[j].v]二edge[j].u;boolflag=1;〃推断是否含有负权回路forinti=1;i=edgenum;++iifdis[edge[i].v]dis[edge[i].u]+edge[i].costflag=0;break;}returnflag;voidprint_pathintroot〃打印最短路的路径反向whileroot!=pre[root]〃前驱printf%d--”,root;root二pre[root];}ifroot==pre[root]printf%d\n/root;}intmainscanf%d%d%dznodenumzedgenumoriginal;pre[original]二original;forinti=1;i=edgenum;++iscanf%d%d%dzedge[i].uzedge[i].vedge[i].cost;ifBellman_Fordforinti=1;i=nodenum;++i〃每个点最短路printf1%d\n/dis[i];printfPath:;print_pathi;}elseprintfhavenegativecircle\n;return0;四.SPFA算法用一个队列来进行维护初始时将源加入队列每次从队列中取出一个元素,并对全部与他相邻的点进行松弛,若某个相邻的点松弛胜利,则将其入队直到队列为空时算法结束;这个算法,简洁的说就是队列优化的bellman-ford采用了每个点不会更新次数太多的特点创造的此算法看我上面那个图,只有相邻点更新了,该点才有可能更新代码参见五趣闻整理该篇博文的时候,一哥们发布网站到我们群,网站很精致,一牛神acmol使用fork炸弹,结果服务器立马挂啦,更改后又挂啦,目测目前无限挂中作者张朋飞出处本文版权归作者张朋飞全部,欢迎转载和商用,但未经作者同意必需保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.
(1)迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最终一行,就是next点)递增次序产生最短路径先把V分成两组・S:已求出最短路径的顶点的集合・V-S=T:尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中,依据可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和(反证法可证,说实话,真不明白哦\
(2)求最短路径步骤.初使时令S={VO}T={其余顶点}T中顶点对应的距离值,若存在VOVi为VOVi弧上的权值(和SPFA初始化方式不同),若不存在VOVi为Infe.从T中选取一个其距离值为最小的顶点W(贪心体现在此处),加入S(留意不是直接从S集合中选取,理解这个对于理解vis数组的作用至关重要),对T中顶点的距离值进行修改若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,贝U修改此距离值(上面两个并列for循环,使用最小点更新X.重复上述步骤,直到S中包含全部顶点,即S=V为止(说明最外层是除起点外的遍历\下面是上图的求解过程,按列来看,第一列是初始化过程,最终一行是每次求得的next点3问题Dijkstar能否处理负权边?来自《图论》答案是不能,这与贪心选择性质有关ps:貌似还是动态规划啊,晕了每次都找一个距源点最近的点dmin然后将该距离定为这个点到源点的最短路径旦假如存在负权边,那就有可能先通过并不是距源点最近的一个次优点dmin再通过这个负权边LL0,使得路径之和更小dmin1+Ldmin,则dmirf+L成为最短路径,并不是dmin这样dijkstra就被冏掉了比如n=3邻接矩阵0340-2-20用dijkstra求得d[l2]=3事实上d[l2]=2就是通过了132使得路径减小不知道讲得清晰不清晰Floyd算法参考了南阳理工牛帅目前在新浪的博客Floyd算法的基本思想如下从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B2是从A经过若干个节点到B所以,我们假设distAB为节点A到节点B的最短路径的距离,对于每一个节点K我们检查distAK+distKBdistAB是否成立,假如成立,证明从A到K再到B的路径比A直接至I」B的路径短,我们便设置distAB=distAK+distKB这样一来,当我们遍历完全部节点KdistAB中纪录的便是A到B的最短路径的距离很简洁吧,代码看起来可能像下面这样:forinti=0;in;++i{forintj=0;jn;++j{forintk=0;kn;++k{ifdist[i][k]+dist[k][j]dist[i][j]{dist[i][j]=dist[i][k]+dist[k][j];}但是这里我们要留意循环的嵌套挨次,假如把检查全部节点K放在最内层,那么结果将是不正确的,为什么呢?由于这样便过早的把i至!Jj的最短路径确定下来了,而当后面存在更短的路径时,已经不再会更新了让我们来看一个例子,看下图:图中红色的数字代表边的权重假如我们在最内层检查全部节点K那么对于A-B我们只能发觉一条路径,就是A-B路径距离为9而这明显是不正确的,真实的最短路径是A-D-C-B路径距离为6造成错误的缘由就是我们把检查全部节点K放在最内层,造成过早的把A到B的最短路径确定下来了,当确定A-B的最短路径时distAC尚未被计算所以,我们需要改写循环挨次,如下ps:个人觉得,这和银行家算法推断平安状态每种资源去测试全部线程,树状数组更新更新全部相关项一样的思想forintk=0;kn;++k{forinti=0;in;++i{forintj=0;jn;++j{实际中为防止溢出,往往需要选推断dist[i][k]^ndist[k][j都不是Inf只要一个是Inf那么就确定不必更新*/ifdist[i][k]+dist[k][j]dist[i][j]{dist[i][j]=dist[i][k]+dist[k][j];假如还是看不懂,那就用草稿纸模拟一遍,之后你就会豁然开朗半个小时足矣早知道的话会节约很多个半小时了萼再来看路径保存问题voidfloyd{forinti=l;i=n;i++{forintj=l;j=n;j++{ifmap[i][j]==Inf{path皿=〃表示i-j不通}else{forintk=l;k=n;k++{forinti=l;i=n;i++{forintj=l;j=n;j++{if!dist[i][k]==Inf||dist[k][j]==Inf8tdist[i][j]dist[i][k]+dist[k][j]{dist[i][j]=dist[i][k]+dist[k][j];path[i][k]=i;path[i][j]=path[k][j];voidprintPathintfromintto{/*这是倒序输出,若想正序可放入栈中,然后输出*这样的输出为什么正确呢?个人认为用到了最优子结构性质即最短路径的子路径仍旧是最短路径/whilepath[from][to]!=from{System.out.printpath[from][to]+to=path[from][to];《数据结构》课本上的那种方式我现在还是不想看,看着不舒适……Floyd算法另一种理解DP为理论爱好者预备的,上面这个形式的算法其实是Floyd算法的精简版而真正的Floyd算法是一种基于DPDynamicProgramming的最短路径算法设图G中n个顶点的编号为1到n0令c[ijk]表示从i至射的最短路径的长度,其中k表示该路径中的最大顶点,也就是说c[ijk]这条最短路径所通过的中间顶点最大不超过ke因此,假如G中包含边ij则c[ij0]二边ij的长度;若i=j,则c[ijO]=O;假如G中不包含边ij则cij0=+8c[ijn]则是从i到j的最短路径的长度对于任意的k0通过分析可以得到中间顶点不超过k的i至!Jj的最短路径有两种可能该路径含或不含中间顶点k0若不含,则该路径长度应为c[ijk-1]否则长度为c[ikk-1]+c[kJk-l]oc[ijk]可取两者中的最小值状态转移方程c[ijk]=min{c[ijk-1]c[ikk-l]+c[kjk-1]}k0o这样,问题便具有了最优子结构性质,可以用动态规划方法来求解看另一个DP直接引用王老师课件说了这么多,信任读者已经跃跃欲试了,咱们看一道例题,以ZOJ1092为例给你一组我国和我国间的部分货币汇率兑换表,问你是否存在一种方式,从一种货币动身,经过一系列的货币兑换,最终返回该货币时大于动身时的数值ps:这就是所谓的投机倒把吧,下面是一组输入3〃我国数。