最短路算法(图论).ppt

图算法及其在通信网中的应用 王晟博士教授博导 part05 最短路算法 2009年春季图算法及其在通信网络中的应用 2 55 最短路算法 1 2 label setting算法 label correcting算法 毫无疑问 重点将是以dijkstra算法为代表的label setting算法 2009年春季图算法及其在通信网络中的应用 3 55 label setting算法 4 基本dijkstra算法 1 2 3 5 分析 analysis 扩展 extension 加速 speedup 应用 application 2009年春季图算法及其在通信网络中的应用 4 55 基本dijkstra算法 dijkstra算法是本课程的核心内容 务必要掌握其思想和具体的编程方法 问题分析 代码设计 算法示例 求解思路 伪码描述 dijkstra算法 2009年春季图算法及其在通信网络中的应用 5 55 问题描述 所有这些最短路构成的是一个怎样的子图 为什么一定是树 最短路径树是生成树么 最短路径树是最小生成树么 2009年春季图算法及其在通信网络中的应用 6 55 dijkstra的求解思路 如何维护最短路径树 如何选择顶点 如何更新距离标记 2009年春季图算法及其在通信网络中的应用 7 55 伪码描述 d j 顶点j的距离标记 p j 顶点j在最短路径树上的前继点 s 最短路径树上的顶点集合 2009年春季图算法及其在通信网络中的应用 8 55 怎样根据得到的这些信息重构出最短路径 dijkstra算法示例 0 c s 2 s 4 s s sa sae saed saedb saedbc 2 s 2 s 6 a 6 a 6 a 6 a 6 d 6 d 6 d 4 a 4 a 4 a 4 s 3 a 3 a a 6 a 4 a 3 a e d 6 d b 每条边被检查了 被描黑 几次 如果放松 连通图 假设 如何改进代码 2009年春季图算法及其在通信网络中的应用 9 55 dijkstra算法代码设计 dijkstraalg d j 和p j 如何管理 findmin update 2009年春季图算法及其在通信网络中的应用 10 55 dijkstraalg源码 一 classcgraph private intnumvertex numedge listincidentlist 所有的边mapmapvid vertex 所有的顶点listlisttempmark 暂时标记的顶点集合map mapvid listedge 记录与顶点关联的出度边update intvid public cgraph char inputfile cgraph listlistedge cgraph cgraph classcvertex public intd intp intid cvertex d infinity p null cvertex boolpvertexcomp cvertex x cvertex y if x dd returntrue returnfalse 如果sort的是对象本身 可以用重载 来实现 这里sort的是对象指针 所以写了个外部函数 2009年春季图算法及其在通信网络中的应用 11 55 dijkstraalg源码 二 voidcgraph dijkstra ints map iteratori iend iend mapvid vertex end for i mapvid vertex begin i iend i if i second id s i second d 0 listtempmark pushback i second update s while listtempmark empty listtempmark sort pvertexcomp intj listtempmark begin id listtempmark popfront update j voidcgraph update intv listledge mapvid listedge v list iteratori iend iend ledge end for i ledge begin i iend i intw i getweight cvertex h mapvid vertex i gethead cvertex t mapvid vertex v if t d wd h d t d w h p v 2009年春季图算法及其在通信网络中的应用 12 55 label setting算法 4 基本dijkstra算法 1 2 3 5 分析 analysis 扩展 extension 加速 speedup 应用 application 2009年春季图算法及其在通信网络中的应用 13 55 分析 analysis 正确性分析和复杂度分析是算法分析中两个主要的内容 复杂度分析 正确性分析 dijkstra算法分析 2009年春季图算法及其在通信网络中的应用 14 55 正确性分析 问题1 dijkstra算法求出的是从s到其他顶点的最短路么 第一次循环 k 1 时 dijkstra算法求出的路径是什么 它是从s出发的最短路么 假定第k次循环求得了第k条最短路 问第k 1次循环求得的是第k 1短的路径么 问题2 dijkstra算法求出的是从s出发的前n条最短路 宿点必须不同 么 yes ofcourse yes itis 2009年春季图算法及其在通信网络中的应用 15 55 复杂度分析 2 2n n 总的操作次数为 2n n n 1 2 n m 结论 dijkstra算法的复杂度为o n2 2009年春季图算法及其在通信网络中的应用 16 55 label setting算法 4 基本dijkstra算法 1 2 3 5 分析 analysis 扩展 extension 加速 speedup 应用 application 2009年春季图算法及其在通信网络中的应用 17 55 扩展 extension 针对不同问题的物理意义 通过扩展dijkstra算法来达到求解目的 单源单宿最短路问题 最短分离路径对问题 带宽约束最短路问题 最大通过率路径问题 dijkstra算法扩展 2009年春季图算法及其在通信网络中的应用 18 55 单源单宿最短路 2009年春季图算法及其在通信网络中的应用 19 55 最大通过率路径 2009年春季图算法及其在通信网络中的应用 20 55 带宽约束下的最短路 2009年春季图算法及其在通信网络中的应用 21 55 最短分离路径对 shortestdisjointpathpair b s c d 4 4 1 1 1 算法不完备 b a c d 4 4 1 1 1 e 8 8 不是最佳解 b a c d 4 4 1 1 1 b a c d 4 4 1 1 1 2009年春季图算法及其在通信网络中的应用 22 55 label setting算法 4 基本dijkstra算法 1 2 3 5 分析 analysis 扩展 extension 加速 speedup 应用 application 2009年春季图算法及其在通信网络中的应用 23 55 加速 speedup 本课程略去了利用各种 堆 数据结构来实现dijkstra算法加速的内容 着重讲一种理论上有效 且有趣 的加速方法 以及两种现实中很有效的方法 dial实现 a 算法 双向dijkstra算法 dijkstra算法加速 2009年春季图算法及其在通信网络中的应用 24 55 dial实现 2009年春季图算法及其在通信网络中的应用 25 55 dijkstra算法的dial实现 0 c s 2 s 4 s s sa sae saed saedb saedbc 2 s 2 s 6 a 6 a 6 a 6 a 6 d 6 d 6 d 4 a 4 a 4 a 4 s 3 a 3 a a 6 a 4 a 3 a e d 6 d b a b c d e a e b d e c 2009年春季图算法及其在通信网络中的应用 26 55 实现细节提示 难点1 基于桶的findmin 难点2 桶的更新 桶的实现 map mapbuckets 指向桶的迭代器map iteratoritbucket 2009年春季图算法及其在通信网络中的应用 27 55 加速 speedup 本课程略去了利用各种 堆 数据结构来实现dijkstra算法加速的内容 着重讲一种理论上有效 且有趣 的加速方法 以及两者现实中很有效的方法 dial实现 a 算法 双向dijkstra算法 dijkstra算法加速 2009年春季图算法及其在通信网络中的应用 28 55 反向dijkstra算法 注意 cgraph中的mapvid listedge只记录了出度边 另外构造一个类似的数据结构 记录每个顶点的入度边 mapvid listrevedge 在进行update时不按mapvid listedge来更新 而是按照后一个数据结构来更新 dijkstra算法 反向dijkstra算法 这就是所谓反向dijkstra算法 2009年春季图算法及其在通信网络中的应用 29 55 双向dijkstra算法 交集为c 但sacd的距离大于sabd 2009年春季图算法及其在通信网络中的应用 30 55 实现细节提示 难点1 要改变循环体 难点3 拼凑和比较 难点2 要增加数据结构 2009年春季图算法及其在通信网络中的应用 31 55 研究性project 2009年春季图算法及其在通信网络中的应用 32 55 加速 speedup 本课程略去了利用各种 堆 数据结构来实现dijkstra算法加速的内容 着重讲一种理论上有效 且有趣 的加速方法 以及两者现实中很有效的方法 dial实现 a 算法 双向dijkstra算法 dijkstra算法加速 2009年春季图算法及其在通信网络中的应用 33 55 a 算法 2009年春季图算法及其在通信网络中的应用 34 55 label setting算法 4 基本dijkstra算法 1 2 3 5 分析 analysis 扩展 extension 加速 speedup 应用 application 2009年春季图算法及其在通信网络中的应用 35 55 应用 链路状态路由协议 ospf openshortestpathfirst 协议是ip网络中链路状态协议的代表 其中采用的就是dijkstra算法 路由器如何实现转发 什么情况下不一致 分布式判决能否一致 转发表是怎么来的 怎样应用dijkstra算法 ospf协议 2009年春季图算法及其在通信网络中的应用 36 55 转发表 路由器r的转发表 c a hi 对每个包进行独立的转发判决 每个包都自己描述自己 怎么可能 如何描述 如何转发 目的地址 转发表 什么是转发表 因为端口2对应的链路在从r到a的最短路上 dijkstra算法 静态配置无法适应动态变化 所以采用一个协议 由每个路由器动态 分布式地自动获取 更新 2009年春季图算法及其在通信网络中的应用 37 55 链路状态协议 2 1 3 4 5 6 4 3 5 6 1 1 4 2 10 22 a c b d 链路状态更新是定时的 或检测到变化 最终所有路由器都获得了全局拓扑信息 2009年春季图算法及其在通信网络中的应用 38 55 分布式判决的一致性 3 1 1 9 3 9 不会的 因为最短路的子路径必然也是最短路 这不是不一致 因为两条路径权重一样 是的 这样会导致不一致 d知道该变化 但a不知道 如果a知道 会有什么不一样 但是 链路状态协议就是为了保证不会出现这种情况 a以为到f的最短路 e以为到f的最短路 会出现这种情况么 不一定 因为链路状态的更新是需要时间的 更新完成以前就可能出现不一致 最典型的例子就是链路失效 链路发生失效后 e知道 而d不知道 e以为到c的最短路是什么 d以为到c的最短路是什么 在d获知状态更新之前 目的为c的分组路由成环 延迟 丢失 失效的快速恢复是前沿课题 2009年春季图算法及其在通信网络中的应用 39 55 最短路算法 1 2 label setting算法 label correcting算法 dijkstra算法只适用于正权重图 针对具有负权重 甚至负圈 的图 该怎么办 2009年春季图算法及其在通信网络中的应用 40 55 label correcting算法 负权重 1 2 3 5 一般的label correcting bellman ford算法 应用 2009年春季图算法及其在通信网络中的应用 41 55 负权重 之所以findmin得到的顶点可以被永久标记 因为该顶点的距离不可能被改进了 如果存在负权重 这个逻辑不再成立 虽然通信网络中很少会出现负权重 但在其他问题中有可能 algorithmsinjava 3rded 21 7节有这样一个例子 如果不要求解必须为简单路径 那么不存在最短路 如果要求解必须为简单路径 那么该问题是np完全问题 与最长路问题一样难 label correcting算法就能达到这个目的 bellman ford算法是label correcting算法的一个特例 工程中 一般用dijkstra算法 因为它快 当出现负权重时 用bellman ford算法 2009年春季图算法及其在通信网络中的应用 42 55 label correcting算法 负权重 1 2 3 5 一般的label correcting bellman ford算法 应用 2009年春季图算法及其在通信网络中的应用 43 55 基本思想 必要性 如果所有距离标记等于最短路的距离 那么它们必然满足上述条件 证明 如果d j 大于d i we 那么至少存在一条路径s i j的距离小于d j 矛盾 充分性 如果所有距离标记都满足上述条件 那么它们就是最短路的距离 证明 任取一条p s j 该路径上的每条边都可以写出上述不等式 求和可知 d j 是所有p s j 的距离下限 2009年春季图算法及其在通信网络中的应用 44 55 一般的label correcting算法 正确性 该算法可以在有限步骤内收敛到最佳解 复杂度 最坏复杂度为o n2c 灵活性 可以用任意方式 顺序检查边 都能保证收敛 但是 总得有个具体的方法吧 况且 就没有复杂度更低的实现方法了么 2009年春季图算法及其在通信网络中的应用 45 55 label correcting算法 负权重 1 2 3 5 一般的label correcting bellman ford算法 应用 2009年春季图算法及其在通信网络中的应用 46 55 fifo实现 bellman ford 1 s到任一其他顶点的最短路径最多n 1跳 即经过n 1条边 除非存在负圈 2 假如s到j实际上的最短路有k跳 那么k轮循环后 d j 必然会被更新为d j d x 表示s到x的最短路的距离 上述事实意味着 该算法最多经过n 1轮循环就可以保证所有的距离标记都更新为最佳值 除非存在负圈 第一次循环 k 1 后 具有最短路跳数为1的那些顶点的距离标记会被更新为最佳值么 yes ofcourse 假定第k次循环后 所有具有最短路跳数小于等于k的那些顶点标记都被更新为最佳值了 问k 1次循环后 还是这样么 yes itis k轮后 必有d u d u k 1轮检查e u v 时 d v d u we d v d u we k 1轮结束后 必有d v d u we d v 这不可能 因为与假设矛盾 2009年春季图算法及其在通信网络中的应用 47 55 加速 0 3 3 3 2 5 3 6 9 4 6 第一轮结束后 顶点s和c没有被更新 第二轮呢 除了c和e外 都没有更新 2 第三轮呢 所有顶点都没有更新 第四 五和六轮呢 浪费 0 list s 3 list list a 6 list af 3 list afe list fe 5 list feb 4 list eb 6 list ebd list bd list d list 2 list e 9 list ec list c list 2009年春季图算法及其在通信网络中的应用 48 55 label correcting算法 负权重 1 2 3 5 一般的label correcting bellman ford算法 应用 2009年春季图算法及其在通信网络中的应用 49 55 应用 距离矢量路由协议 当i的反向邻接点发生了更新时 当i的正向邻接点到d的距离发生了更新时 c a 距离矢量更新消息 b a a c a b c d b c b d c b d b d c 这只是第1轮 每当路由器发生了