第六讲最短路精选PPT.ppt
第六讲最短路第1页，此课件共56页哦声明本系列教学幻灯片属于刘汝佳、黄亮著算法艺术与信息学竞赛配套幻灯片本幻灯片可从本书blog上免费下载，即使您并未购买本书.若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用有任何意见，欢迎在blog上评论Blog地址：http:/第2页，此课件共56页哦内容介绍一、SSSP问题二、dijkstra算法三、Bellman-ford算法四、差分约束系统五、Gabow的变尺度算法六、APSP问题七、floyd-warshall算法八、Johnson算法第3页，此课件共56页哦一、单源最短路问题一、单源最短路问题(SSSP)第4页，此课件共56页哦SSSP给加权图和一个起点s,求s到所有点的最短路(边权和最小的路径)最短路有环吗正环:何必呢,删除环则得到更短路负环:无最短路,因为可以沿负环兜圈子第5页，此课件共56页哦最优性原理最优性原理:若最短路uv经过中间结点w,则uw和wv的路径分别是u到w和w到v的最短路.意义:贪心、动态规划第6页，此课件共56页哦最短路的表示最短路的表示s到所有点的最短路不需要分别表示最短路树:到每个点都沿着树上的唯一路径走实际代码:记录每个点的父亲predu即可输出最短路:从终点沿着predu递推回起点第7页，此课件共56页哦为什么单源最短路形成树?考虑下图如果uz的路只取一条即可第8页，此课件共56页哦最短路树和最小生成树第9页，此课件共56页哦一般SSSP算法临时最短路存在此路，即真实的最短路长度不大于此路长度但是有可能有更短的，所以此路长度只是一个上界此路长度只是一个上界给定起点s，对于每个顶点v，定义dist(v)为临时最短路树中s-v的长度pred(v)为临时最短路树中s-v中v的前驱初始化:dist(s)=0,pred(s)=NULL,初始化:所有其他dist(v)为无穷，pred(v)=NULLdist(v)称为点v的标号(label),它是最短路的上界基本想法:让标号不断趋近,最终达到最短路第10页，此课件共56页哦一般SSSP算法什么样的标号明显可以改进(趋近最短路)?一条边(u,v)被称为紧的(tense),如果dist(u)+w(u,v)dist(v)可以松弛：dist(v)=dist(u)+w(u,v),pred(v)=u结论存在紧的边，一定没有正确的求出最短路树不存在紧的边，一定正确的求出最短路树第11页，此课件共56页哦一般SSSP算法的正确性(u,v)被称为紧的：dist(u)+w(u,v)dist(v)不存在紧边，一定求出最短路树即由pred表示出的路径上所有边权和等于dist(v)（归纳于松弛的次数）结束时对s到v的任意路sv，dist(v)=w(sv)归纳于sv所含边数，假设su-v（u=pred(v)）dist(u)=w(su)，两边加w(u,v)得：dist(u)+w(u,v)=w(sv)。因为无紧边，所以dist(v)=dist(u)+w(u,v)=w(sv)第12页，此课件共56页哦一般SSSP算法的结束条件刚才已经证明结束时dist(v)和pred(v)相容若算法结束，则结果正确算法何时能结束呢？含负圈（能到达的），则永不结束，因为在一次松弛以后，负圈上一定有紧边（反证）不含负圈，则一定结束，因为要么减少一个无穷dist值，要么让所有有限dist值之和至少减少一个“不太小的正值”。第13页，此课件共56页哦一般SSSP算法一般算法可以以任意顺序寻找紧边并松弛收敛时间没有保障解决方案：把结点放到bag中，每次取一个出来检查特殊bag：dijkstra(heap),bellman-ford(queue)第14页，此课件共56页哦二、二、dijkstra算法算法第15页，此课件共56页哦Dijkstra算法E.W.Dijkstra.A note on two problems in connection with graphs.Num.Math.,1:269-271,1959原始是O(n2),可以用各种形式的堆加速第16页，此课件共56页哦Dijkstra算法标号设定算法:每次dist(v)最小的一个恰好等于它的最短值，予以固定正确性证明(注意为什么需要权非负非负)第17页，此课件共56页哦第18页，此课件共56页哦时间复杂度Dijkstra算法使用了一个优先队列INSERT(line 3),每个结点一次EXTRACT-MIN,每个结点一次DECREASE-KEY(line 8,在RELAX过程中),一共|E|次直接实现:O(V2)二项堆:O(ElogV)Fibonacci堆:O(E+VlogV)第19页，此课件共56页哦练习给有向加权图,边权值为0,1之间的实数,代表边的可靠性(各边的可靠性独立).找出s到t的路径中可靠性最大的一条(总可靠性等于每条边可靠性之乘积)假设边权值范围为1,2,3,W把每条边拆成w(u,v)条边串联,然后BFS直接修改dijkstra得到O(VW+E)的算法优化到O(V+E)lgW)从s出发的边有可能有负边(但无负环),其他边均为正权.Dijkstra算法能得到最优解吗?第20页，此课件共56页哦应用路的最小公倍数给出一个带权无向图G边权为11 000的整数对于v0到v1的任意一条简单路p,定义s(p)为p上所有边权的最大公约数考虑v0到v1的所有路p1,p2,求所有s(p1),s(p2),的最小公倍数第21页，此课件共56页哦三、三、bellman-ford算法算法第22页，此课件共56页哦SSSP：bellman-ford算法Ford 1956,Bellman 1958,Moore 1959.如有最短路，则每个顶点最多经过一次这条路不超过n-1条边长度为长度为k的路由长度为的路由长度为k-1的路增加一条边得到的路增加一条边得到由最优性原理,只考虑长度为1k-1的最短路算法梗概:每次迭代依次松弛每条边时间复杂度O(Dm)，v为迭代次数(v=n-1)完全图边权在0,1中均匀分布,很大概率D=O(log2n)若某次迭代没进行成功松弛,可立即停止可用dijkstra得到初始dist第23页，此课件共56页哦第24页，此课件共56页哦Yen的修改算法把G中的边(vi,vj)分为两类:f边:i j每次迭代先从v1遍历到v|V|,松弛f边,再从v|V|遍历回v1,松弛b边则最多只需要|V|/2次(取上整)迭代,但不降低时间复杂度第25页，此课件共56页哦练习给出可能有负权的有向加权图,对于每个点v,在O(VE)时间求出离v最近点到它的距离给出有负圈的图,在O(VE)时间内输出圈上的结点列表第26页，此课件共56页哦应用套汇第27页，此课件共56页哦四、差分约束系统四、差分约束系统第28页，此课件共56页哦差分约束系统线性规划(linear programming,LP):给m*n矩阵A、m维向量b和n维向量c,求出x为向量使得Ax=b,且sumcixi最小可行性问题(feasibility problem):只需要任意找出一组满足Ax=b的解向量x差分约束系统(system of difference constraints):A的每行恰好一个1和一个-1,其他元素都是0.相当于关于n个变量的m个差分约束,每个约束都形如xj-xi=bk,其中1=i,j=n,1=k=m.第29页，此课件共56页哦差分约束系统举例左边的可行性问题等价于右边的差分约束系统第30页，此课件共56页哦基本思路定理:给定差分约束系统的一组解,给每个变量加上一个常数d,将得到另外一组解约束图:结点是变量,一个约束对应一条弧,若有弧(u,v),则得到xu后,有xv=xu+w(u,v)第31页，此课件共56页哦算法定理:如果约束图没有负圈,则可取xu为起点v0到u的最短路长;若约束图有负圈,差分约束系统无解.正确性证明无负圈:由松弛条件可证明每个约束得到满足有负圈:把负圈上的约束条件叠加将得到一个矛盾不等式算法步骤构图,得到n+1个结点m+n条边运行bellman-ford,时间 O(n2+mn)第32页，此课件共56页哦练习如何修改bellman-ford算法,使得将它应用在差分约束系统的求解中,使得当m比n小时,时间复杂度可以由O(n2+mn)降为O(mn)如果差分约束中存在等式约束,即xi-xj=bk,如何求解?xi=bk 或者-xi=bk呢?如果限定xi=0,证明bellman-ford算法得到的可行解让xi总和最大化证明bellman-ford算法得到的可行解让maxxi-minxi最小修改算法使得当b取实数时可以得到整数解.如果给定变量子集需要取整数呢?第33页，此课件共56页哦应用出纳员的雇佣24小时营业的超市需要一批出纳员来满足它的需求,每天的不同时段需要不同数目的出纳员给出每小时需要出纳员的最少数R0,R23R(0)表示从午夜到午夜1:00需要出纳员的最少数目，R(1)表示上午1:00到2:00之间需要的每一天，这些数据都是相同的有N人申请这项工作,如果第i个申请者被录用，他将从ti刻开始连续工作8小时计算为满足上述限制需要雇佣的最少出纳员数目i时刻可以有比对应的Ri更多的出纳员在工作第34页，此课件共56页哦分析前i小时的雇佣总数：si(规定s-1=0)第i小时需要的出纳员：ri第i小时申请的人数：ti取(i,j)满足i=(j+8)mod 24,则有不等式0=si si-1 j时 si sj=riI=ri sum当sum固定时,此不等式组是差分约束系统可以枚举sum,也可以二分第35页，此课件共56页哦五、五、Gabow的变尺度算法的变尺度算法第36页，此课件共56页哦变尺度算法变尺度算法(scaling algorithm)广泛的应用在图论算法设计中,其基本思想是先只考虑某相关输入值的最高位,然后考虑前两位、前三位、直到考虑完所有位,则得到正确结果考虑SSSP问题.令k表示需要考虑的位数.一般取k=log2(W+1)(取上整),wi(u,v)表示边权w(u,v)的前i位.(当k=5,w(i,j)=(11001)2时w3(i,j)=(110)2让div表示取wi为权函数时的最短路,则di可以通过di-1用O(E)的时间算出，因此总时间复杂度为O(ElogW)第37页，此课件共56页哦Gabow算法引理引理:若恒有dv=|E|,则d可以在O(E)时间算出.证明:用dijkstra,计数排序,则所有操作都是O(1)Gabow算法首先用O(E)时间算出d1由于wi(u,v)等于2wi-1(u,v)或者2wi-1(u,v)+1,因此对于任意点v,2di-1v=dv=2di-1v+|V|-1对w重加权,wi(u,v)=wi(u,v)+2di-1u-2di-1v则w(u,v)非负,且div=div+2di-1v,且div=|E|因此可以在O(E)时间通过di-1计算di总时间复杂度为O(ElogW)第38页，此课件共56页哦六、每对结点最短路六、每对结点最短路(APSP)第39页，此课件共56页哦APSP基本想法考虑从每个点出发做一次SSSP的时间效率权任意时n次bellman-ford是O(n2m),稠密图时O(n4)思路:动态规划第40页，此课件共56页哦基本动态规划算法di,u,v为u到v最多不超过i条边的最短路长算法一：di,u,v=mindi-1,u,x+w(x,v)，x遍历v的邻居时间复杂度：O(V2E)k短路：di,u,v=sumdi-1,u,x+w(x,v)算法二:di,u,v为u到v最多不超过2i条边的最短路长,则最短路可以在O(n3logn)算出第41页，此课件共56页哦矩阵乘法算法可以通过矩阵乘法计算任两点间最短路第42页，此课件共56页哦基本思想和改进矩阵乘法算法思想:不停加边(算法如下,O(n3)优化时间:二分计算幂.O(n3logn).空间用滚动矩阵O(n2)用Strassen矩阵乘法:O(nlog7logn)第43页，此课件共56页哦练习如何求出有向加权图中边数最少的负圈?第44页，此课件共56页哦七、七、Floyd-warshall算法算法第45页，此课件共56页哦状态设计设di,j,k是在只允许经过结点1k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：最短路经过点k，di,j,k=di,k,k-1+dk,j,k-1最短路不经过点k，di,j,k=di,j,k-1第46页，此课件共56页哦状态方程第47页，此课件共56页哦第48页，此课件共56页哦第49页，此课件共56页哦Floyd-Warshall算法把k放外层循环，可以节省内存注意”无穷大”的运算时间复杂度:O(n3)空间复杂度:O(n2)第50页，此课件共56页哦输出最短路计算出最短路值后,可以用下面的过程可以输出任意两点间的最短路第51页，此课件共56页哦八、八、Johnson算法算法第52页，此课件共56页哦Johnson算法稀疏图中,floyd算法时间效率并不理想重加权目的：权变非负后用dijkstra每条边等量增加可能改变最短路树例子：全部增加2的情况（右图）Johnson算法目标：找到c(v)重加权公式：w(u,v)=c(u)+w(u,v)-c(v)加权后最短路树不变因为对于任意路su,w(su)=w(su)+c(s)-c(u)第53页，此课件共56页哦Johnson算法如何设计cost(v)函数，使所有新权非负？增加人工节点s，直接到所有点，权均为0以s为起点运行bellman-ford，求出dist(v)如果有负权圈，退出，否则对于原图点v，c(v)=dist(v)为什么w(u,v)=dist(u)+w(u,v)-dist(v)非负？如果不是，dist(u)+w(u,v)dist(v)这意味着(u,v)是紧的！第54页，此课件共56页哦算法示意第一行为重加权步骤第二行为每个结点运行dijkstra的结果第55页，此课件共56页哦Johnson算法时间复杂度分析Bellman-ford：O(VE)运行n次dijkstra：O(VE+V2logV)第56页，此课件共56页哦
