知识卡片
非负权最短路贪心定案
对边权非负的图,维护每个顶点当前已知最短路径上界;每轮选取尚未确定且距离最小的顶点 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循环的内循环中,每条边都要被