第六讲最短路(算法艺术).ppt
《第六讲最短路(算法艺术).ppt》由会员分享,可在线阅读,更多相关《第六讲最短路(算法艺术).ppt(56页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 短路 算法 艺术
限制150内