[教育学]图论算法与模型.ppt

图论算法与模型 刘汝佳 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) SSSP：bellman-ford算法 Ford 1956, Bellman 1958, Moore 1959. 如有最短路，则每个顶点最多经过一次 这条路不超过n-1条边 长度为k的路由长度为k-1的路增加一条边得到 由最优性原理, 只考虑长度为1…k-1的最短路 算法梗概: 每次迭代依次松弛每条边 时间复杂度 O(Dm)，v为迭代次数(v=n-1) 完全图边权在[0, 1]中均匀分布, 很大概率D=O(log2n) 若某次迭代没进行成功松弛, 可立即停止 可用dijkstra得到初始dist APSP基本想法 考虑从每个点出发做一次SSSP的时间效率 权任意时n次bellman-ford是O(n2m), 稠密图时O(n4) 思路: 动态规划 状态设计 设d[i,j,k]是在只允许经过结点1…k的情况下i到j的最短路长度, 则它有两种情况： 最短路经过点k，d[i,j,k]=d[i,k,k-1]+d[k,j,k-1] 最短路不经过点k，d[i,j,k]=d[i,j,k-1] Floyd-Warshall算法 把k放外层循环，可以节省内存 注意”无穷大”的运算 时间复杂度: O(n3) 空间复杂度: O(n2) 路的最小公倍数 给出一个带权无向图G 边权为1…1 000的整数 对于v0到v1的任意一条简单路p, 定义s(p)为p上所有边权的最大公约数 考虑v0到v1的所有路p1,p2,…, 求所有s(p1),s(p2),…的最小公倍数 Arbitrage 套汇: 不停的换外汇, 换回来后赚钱(假设无手续费) 如三次兑换: 1*0.7*9.5*0.16=1.0641 给出任意两种货币兑换的比率, 寻找一个方案(必须换回来), 使得比率大于1.01 如果有多种方案, 求长度最短的 分析 本题可以抽象为: 给出正权完全有向图, 找权