第六讲最短路(算法艺术).ppt

《第六讲最短路(算法艺术).ppt》由会员分享，可在线阅读，更多相关《第六讲最短路(算法艺术).ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、算法艺术与信息学竞赛教学幻灯片算法图论第六讲 最短路声明 本系列教学幻灯片属于刘汝佳、黄亮著算法艺术与信息学竞赛配套幻灯片 本幻灯片可从本书blog上免费下载，即使您并未购买本书. 若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用 有任何意见，欢迎在blog上评论 Blog地址：http:/内容介绍一、SSSP问题二、dijkstra算法三、Bellman-ford算法四、差分约束系统五、Gabow的变尺度算法六、APSP问题七、floyd-warshall算法八、Johnson算法一、单源最短路问题一、单源最短路问题(SSSP)SSSP 给加权图

2、和一个起点s, 求s到所有点的最短路(边权和最小的路径) 最短路有环吗 正环: 何必呢, 删除环则得到更短路 负环: 无最短路, 因为可以沿负环兜圈子最优性原理 最优性原理: 若最短路uv经过中间结点w, 则uw和wv的路径分别是u到w和w到v的最短路. 意义: 贪心、动态规划最短路的表示 最短路的表示 s到所有点的最短路不需要分别表示 最短路树: 到每个点都沿着树上的唯一路径走 实际代码: 记录每个点的父亲predu即可 输出最短路: 从终点沿着predu递推回起点为什么单源最短路形成树? 考虑下图 如果uz的路只取一条即可最短路树和最小生成树一般SSSP算法 临时最短路 存在此路，即真实的

3、最短路长度不大于此路长度 但是有可能有更短的，所以此路长度只是一个上界此路长度只是一个上界 给定起点s，对于每个顶点v，定义 dist(v)为临时最短路树中s-v的长度 pred(v)为临时最短路树中s-v中v的前驱 初始化: dist(s)=0, pred(s)=NULL, 初始化: 所有其他dist(v)为无穷，pred(v)=NULL dist(v)称为点v的标号(label), 它是最短路的上界 基本想法: 让标号不断趋近, 最终达到最短路一般SSSP算法 什么样的标号明显可以改进(趋近最短路)? 一条边(u,v)被称为紧的(tense), 如果dist(u)+w(u,v)dist(v

4、) 可以松弛：dist(v)=dist(u)+w(u,v), pred(v)=u 结论 存在紧的边，一定没有正确的求出最短路树 不存在紧的边，一定正确的求出最短路树一般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)

5、=dist(u)+w(u,v)=w(sv)一般SSSP算法的结束条件 刚才已经证明 结束时dist(v)和pred(v)相容 若算法结束，则结果正确 算法何时能结束呢？ 含负圈（能到达的），则永不结束，因为在一次松弛以后，负圈上一定有紧边（反证） 不含负圈，则一定结束，因为要么减少一个无穷dist值，要么让所有有限dist值之和至少减少一个“不太小的正值”。一般SSSP算法 一般算法 可以以任意顺序寻找紧边并松弛 收敛时间没有保障 解决方案：把结点放到bag中，每次取一个出来检查 特殊bag：dijkstra(heap), bellman-ford(queue)二、二、dijkstra算法算法

6、Dijkstra算法 E.W.Dijkstra. A note on two problems in connection with graphs. Num.Math.,1:269-271, 1959 原始是O(n2), 可以用各种形式的堆加速Dijkstra算法 标号设定算法: 每次dist(v)最小的一个恰好等于它的最短值，予以固定 正确性证明 (注意为什么需要权非负非负)时间复杂度 Dijkstra算法使用了一个优先队列 INSERT (line 3), 每个结点一次 EXTRACT-MIN, 每个结点一次 DECREASE-KEY (line 8, 在RELAX过程中), 一共|E|次

7、 直接实现: O(V2) 二项堆: O(ElogV) Fibonacci堆: O(E+VlogV)练习 给有向加权图, 边权值为0,1之间的实数, 代表边的可靠性(各边的可靠性独立). 找出s到t的路径中可靠性最大的一条(总可靠性等于每条边可靠性之乘积) 假设边权值范围为1, 2, 3, , W 把每条边拆成w(u,v)条边串联, 然后BFS 直接修改dijkstra得到O(VW+E)的算法 优化到O(V+E)lgW) 从s出发的边有可能有负边(但无负环), 其他边均为正权. Dijkstra算法能得到最优解吗?应用路的最小公倍数 给出一个带权无向图G 边权为11 000的整数 对于v0到v1

8、的任意一条简单路p, 定义s(p)为p上所有边权的最大公约数 考虑v0到v1的所有路p1,p2, 求所有s(p1),s(p2),的最小公倍数三、三、bellman-ford算法算法SSSP：bellman-ford算法 Ford 1956, Bellman 1958, Moore 1959. 如有最短路，则每个顶点最多经过一次 这条路不超过n-1条边长度为长度为k的路由长度为的路由长度为k-1的路增加一条边得到的路增加一条边得到 由最优性原理, 只考虑长度为1k-1的最短路 算法梗概: 每次迭代依次松弛每条边 时间复杂度 O(Dm)，v为迭代次数(v=n-1) 完全图边权在0, 1中均匀分布,

9、 很大概率D=O(log2n) 若某次迭代没进行成功松弛, 可立即停止 可用dijkstra得到初始distYen的修改算法 把G中的边(vi, vj)分为两类: f边: i j 每次迭代先从v1遍历到v|V|, 松弛f边, 再从v|V|遍历回v1, 松弛b边 则最多只需要|V|/2次(取上整)迭代, 但不降低时间复杂度练习 给出可能有负权的有向加权图, 对于每个点v, 在O(VE)时间求出离v最近点到它的距离 给出有负圈的图, 在O(VE)时间内输出圈上的结点列表应用套汇四、差分约束系统四、差分约束系统差分约束系统 线性规划(linear programming, LP): 给m*n矩阵A、

10、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.差分约束系统举例 左边的可行性问题等价于右边的差分约束系统基本思路 定理: 给定差分约束系统的一组解, 给每个变量加上一个常数d, 将得到另外一组解 约束图: 结点是变量, 一个约束对应一

11、条弧, 若有弧(u, v), 则得到xu后, 有xv = xu + w(u,v)算法 定理: 如果约束图没有负圈, 则可取xu为起点v0到u的最短路长; 若约束图有负圈, 差分约束系统无解. 正确性证明 无负圈: 由松弛条件可证明每个约束得到满足 有负圈: 把负圈上的约束条件叠加将得到一个矛盾不等式 算法步骤 构图, 得到n+1个结点m+n条边 运行bellman-ford, 时间 O(n2+mn)练习 如何修改bellman-ford算法, 使得将它应用在差分约束系统的求解中, 使得当m比n小时, 时间复杂度可以由O(n2+mn)降为O(mn) 如果差分约束中存在等式约束, 即xi-xj=b

12、k, 如何求解? xi=bk 或者-xi=bk呢? 如果限定xi=0, 证明bellman-ford算法得到的可行解让xi总和最大化 证明bellman-ford算法得到的可行解让maxxi-minxi最小 修改算法使得当b取实数时可以得到整数解. 如果给定变量子集需要取整数呢?应用出纳员的雇佣 24小时营业的超市需要一批出纳员来满足它的需求, 每天的不同时段需要不同数目的出纳员 给出每小时需要出纳员的最少数R0, , R23 R(0)表示从午夜到午夜1:00需要出纳员的最少数目， R(1)表示上午1:00到2:00之间需要的 每一天，这些数据都是相同的 有N人申请这项工作, 如果第i个申请者

13、被录用，他将从ti刻开始连续工作8小时 计算为满足上述限制需要雇佣的最少出纳员数目 i时刻可以有比对应的Ri更多的出纳员在工作分析 前i小时的雇佣总数：si (规定s-1 = 0) 第i小时需要的出纳员：ri 第i小时申请的人数：ti 取(i,j)满足i = (j+8) mod 24, 则有不等式 0 = si si-1 j时 si sj = ri I = ri sum 当sum固定时, 此不等式组是差分约束系统 可以枚举sum, 也可以二分五、五、Gabow的变尺度算法的变尺度算法变尺度算法 变尺度算法(scaling algorithm)广泛的应用在图论算法设计中, 其基本思想是先只考虑某

14、相关输入值的最高位, 然后考虑前两位、前三位、直到考虑完所有位, 则得到正确结果 考虑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)Gabow算法 引理引理: 若恒有dv =|E|, 则d可以在O(E)时间算出.证明: 用dijkstra, 计数排序, 则所有操作都是O(1) Gabow算法 首先用O(E)时间算出d1

15、 由于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)六、每对结点最短路六、每对结点最短路(APSP)APSP基本想法 考虑从每个点出发做一次SSSP的时间效率 权任意时n次bellman-ford是O(n2m), 稠密图时O(n4) 思路: 动态规划基本动态规划算法 di,u,v为u到

16、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)算出矩阵乘法算法 可以通过矩阵乘法计算任两点间最短路基本思想和改进 矩阵乘法算法思想:不停加边(算法如下, O(n3) 优化 时间: 二分计算幂. O(n3logn). 空间用滚动矩阵O(n2) 用Strassen矩阵乘法: O(nlog7logn)练习 如何求出有向加权图中边数最少的负圈?七、七、Floyd-

17、warshall算法算法状态设计 设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状态方程Floyd-Warshall算法 把k放外层循环，可以节省内存 注意”无穷大”的运算 时间复杂度: O(n3) 空间复杂度: O(n2)输出最短路 计算出最短路值后,可以用下面的过程可以输出任意两点间的最短路八、八、Johnson算法算法Johnson算法 稀疏图中, floyd算法时间效率并不理想 重加权 目的：权变非负后用dijkst

18、ra 每条边等量增加可能改变最短路树 例子：全部增加2的情况（右图） Johnson算法 目标：找到c(v) 重加权公式：w(u,v)=c(u)+w(u,v)-c(v) 加权后最短路树不变 因为对于任意路su, w(su)=w(su)+c(s)-c(u)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)是紧的！算法示意 第一行为重加权步骤 第二行为每个结点运行dijkstra的结果Johnson算法 时间复杂度分析 Bellman-ford：O(VE) 运行n次dijkstra：O(VE+V2logV)