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

《算法艺术与信息学竞赛》教学幻灯片 算法图论 第六讲 最短路 声明 本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片 本幻灯片可从本书blog上免费下载，即使您并未购买本书. 若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用 有任何意见，欢迎在blog上评论 Blog地址： 内容介绍 一、SSSP问题 二、dijkstra算法 三、Bellman-ford算法 四、差分约束系统 五、Gabow的变尺度算法 六、APSP问题 七、floyd-warshall算法 八、Johnson算法 一、单源最短路问题(SSSP) SSSP 给加权图和一个起点s, 求s到所有点的最短路(边权和最小的路径) 最短路有环吗 正环: 何必呢, 删除环则得到更短路 负环: 无最短路, 因为可以沿负环兜圈子 最优性原理 最优性原理: 若最短路u?v经过中间结点w, 则u?w和w?v的路径分别是u到w和w到v的最短路. 意义: 贪心、动态规划 最短路的表示 最短路的表示 s到所有点的最短路不需要分别表示 最短路树: 到每个点都沿着树上的唯一路径走 实际代码: 记录每个点的父亲pred[u]即可 输出最短路: 从终点沿着pred[u]递推回起点 为什么单源最短路形成树? 考虑下图 如果u?z的路只取一条即可 最短路树和最小生成树 一般SSSP算法 临时最短路 存在此路，即真实的最短路长度不大于此路长度 但是有可能有更短的，所以此路长度只是一个上界 给定起点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) 可以松弛：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的任意路s?v，dist(v)=w(s?v) 归纳于s?v所含边数，假设s?u-v（u=pred(v)） dist(u)=w(s?u)，两边加w(u,v)得： dist(u)+w(u,v)=w(s?v)。因为无紧边，所以 dist(v)=dist(u)+w(u,v)=w(s?v) 一般SSSP算法的结束条件 刚才已经证明 结束时dist(v)和pred(v)相容 若算法结束，则结果正确 算法何时能结束呢？ 含负圈（能到达的），则永不结束，因为在一次松弛以后，负圈上一定有紧边（反证） 不含负圈，则一定结束，因为要么减少一个无穷dist值，要么让所有有限dist值之和至少减少一个“不太小的正值”。 一般SSSP算法 一般算法 可以以任意顺序寻找紧边并松弛 收敛时间没有保障 解决方案：把结点放到bag中，每次取一个出来检查 特殊bag：dijkstra(heap), bellman-ford(queue) 二、dijkstra算法 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|次 直接实现: O(V2) 二项堆: O(ElogV) Fibonacci堆: O(E+VlogV) 练习 给有向加权图, 边权值为[0,1]之间的实数, 代表边的可靠性(各边的可靠性独立). 找出s到t的路径中可靠性最大的一条(总可靠性等于每条边可靠性之乘积) 假设边权值范围为{1, 2, 3, …, W} 把每条边拆成w(u,v)条边串联, 然后BFS