知识卡片

普通读书笔记卡 · 5654.d.1.f.4.g · 生成模型:未记录

非负权最短路贪心定案

理解等级:中级

对边权非负的图,维护每个顶点当前已知最短路径上界;每轮选取尚未确定且距离最小的顶点 u,将其距离定案,再用 dist[u]+w(u,v) 松弛出边。非负权确保尚未处理的路径不能让已定案顶点变得更短。

源点距离为0,不可达点为无穷;只有需要单目标时,可在目标以最小距离出队并定案后停止。负权边可能破坏该保证,应选择支持负边的算法并处理负环。

161图03292示例通过顶点2更新顶点3的距离为17;二叉堆取最小和decreaseKey各需 O(log V),完整邻接表实现常为 O((V+E) log V)。堆顶读取可为 O(1),但删除最小不是常数。03293–03294没有显式在最小距离为无穷时终止;使用无穷哨兵进行加法前须特别处理。

163比较邻接表加二叉堆 O((V+E) log V) 与每轮扫描顶点的 O(V²+E);若使用邻接矩阵扫描行,整体通常 O(V²)。图03299–03300直接遍历矩阵中的每个权重,必须约定无边哨兵并避免将其当成普通权重参与加法。历史平台的STL优化幅度不能直接推广。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      Dijkstra算法(图6-13)。找到最短路径之后,这个搜索可能会终止。如果近似的结果可以接受,那么我们能够根据启发式的信息来引导搜索,这就是这个算法的一个变种(A*搜索,在第7章讨论)。 本质上,Dijkstra算法贪婪地扩展顶点集S,对于S中的每一个顶点v来说,s到v的最短路径已经计算出来。计

    • · 查看原书依据

      优先队列来存储V-S中的顶点。在这里优先队列是二叉堆,因为我们可以在常数时间寻找到优先级最小的顶点(优先级是顶点到s的距离)。此外,当s到v的最短路径找到之后,dist[v]的值减少,那么堆也必须修改。幸运的是,二叉堆形式的优先队列decreaseKey操作在平均情况下花费时间为O(log q),q

    • · 查看原书依据

      稠密图,使用的是一个邻接矩阵。例6-4中的C++实现更加简单,因为它避免了使用二叉堆。这个版本的效率是由如何快速在V-S中得到最小的dist[]。whilte循环将会执行n次,因为S每次只会增加一个顶点。在V-S中得到最小的dist[u]将要探测n个顶点。注意在while循环的内循环中,每条边都要被

    参考来源

    - 位置:《算法技术手册》第6章《单源最短路径》(spine1574;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1537.html;u159-ch06-008)。 - 结论依据:159全文与160–161的03291–03294伪代码及实现对照实读。 - 原始内容:Dijkstra算法(图6-13)。找到最短路径之后,这个搜索可能会终止。如果近似的结果可以接受,那么我们能够根据启发式的信息来引导搜索,这就是这个算法的一个变种(A*搜索,在第7章讨论)。 本质上,Dijkstra算法贪婪地扩展顶点集S,对于S中的每一个顶点v来说,s到v的最短路径已经计算出来。计 - 位置:《算法技术手册》第6章《解决方案》(spine1575;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1538.html;u161-ch06-008)。 - 结论依据:161图03292示例通过顶点2更新顶点3的距离为17;二叉堆取最小和decreaseKey各需 O(log V),完整邻接表实现常为 O((V+E) log V)。堆顶读取可为 O(1),但删除最小不是常数。03293–03294没有显式在最小距离为无穷时终止;使用无穷哨兵进行加法前须特别处理。 - 原始内容:优先队列来存储V-S中的顶点。在这里优先队列是二叉堆,因为我们可以在常数时间寻找到优先级最小的顶点(优先级是顶点到s的距离)。此外,当s到v的最短路径找到之后,dist[v]的值减少,那么堆也必须修改。幸运的是,二叉堆形式的优先队列decreaseKey操作在平均情况下花费时间为O(log q),q - 位置:《算法技术手册》第6章《分析》(spine1577;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1540.html;u163-ch06-008)。 - 结论依据:163比较邻接表加二叉堆 O((V+E) log V) 与每轮扫描顶点的 O(V²+E);若使用邻接矩阵扫描行,整体通常 O(V²)。图03299–03300直接遍历矩阵中的每个权重,必须约定无边哨兵并避免将其当成普通权重参与加法。历史平台的STL优化幅度不能直接推广。 - 原始内容:稠密图,使用的是一个邻接矩阵。例6-4中的C++实现更加简单,因为它避免了使用二叉堆。这个版本的效率是由如何快速在V-S中得到最小的dist[]。whilte循环将会执行n次,因为S每次只会增加一个顶点。在V-S中得到最小的dist[u]将要探测n个顶点。注意在while循环的内循环中,每条边都要被