算法（61）：Dijsktra算法中的decrease key操作-18.3

Q我想再听你详细讲讲P37页尤其关于什么是decrease keyA好我们专门看第37页。这一页是在比较 Dijkstra 算法以及 Prim 算法因为两者骨架相同在不同优先队列实现下的时间复杂度。它的核心物理原因是你需要一个支持decreaseKey操作的优先队列否则算法会退化。我们分三层来讲这个操作是什么、为什么需要它、以及它如何决定第37页表格里的时间复杂度。1. 什么是decreaseKey在 Dijkstra 算法的relax方法中有一行关键代码javaif (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert(w, distTo[w]);当发现一条更短的路径到达顶点 w 时如果 w 还没在优先队列里第一次发现调用insert。如果 w 已经在优先队列里之前发现过但距离更大调用decreaseKey。decreaseKey(w, newDist)的物理含义是把优先队列中与顶点 w 关联的键值从旧值改小为新值。它的物理动作是通过索引 w 找到它在堆中的位置。修改那个位置的键值。因为键值变小了它需要向上浮动swim直到满足堆序父节点键值 ≤ 子节点键值。2. 为什么需要它不用它会怎样假设你用的是普通的MinPQ它只支持insert和delMin没有decreaseKey。当发现更短路径到 w 时你只能把新的键值作为一个新条目insert(w, newDist)插入堆。旧的、更大的键值条目仍然留在堆里。这会导致两个物理后果堆的规模膨胀同一个顶点可能有多个条目在堆里对应不同时间发现的路径长度。需要额外的失效检查当你从堆里弹出一个顶点时你需要判断这个条目是不是最新的通过比较distTo[v]是否等于堆里存的键值如果是旧的直接丢弃。这就是Lazy Dijkstra懒惰版 Dijkstra的做法。它不需要decreaseKey但代价是堆里最多有 E 个条目因为每条边可能触发一次 insert。空间复杂度从 O(V) 变成 O(E)。时间复杂度变成 O(E log E)而不是 O(E log V)。而decreaseKey的作用就是避免在堆里堆积同一个顶点的旧条目。它直接在原条目上修改键值保持堆的大小始终为 O(V)。3. 为什么普通堆无法高效支持decreaseKey普通的二叉堆底层是一个数组数组里直接存键值。堆的操作swim、sink都是基于数组下标的。问题在于你只知道要修改顶点 w 的键值但你不知道 w 在堆数组的哪个位置。如果没有额外的索引结构你只能线性扫描整个堆数组O(V) 时间去找到 w这会让decreaseKey的代价从 O(log V) 退化到 O(V)。这就是IndexMinPQ索引优先队列被引入的物理原因。它维护了三个平行数组keys[i]索引 i 的当前键值。pq[i]堆中位置 i 存放的是哪个顶点索引。qp[i]顶点索引 i 在堆中的位置反向索引。queue position有了qp[]调用decreaseKey(w, newDist)时更新keys[w] newDist。通过qp[w]直接拿到 w 在堆中的位置 posO(1)。调用swim(pos)在 O(log V) 时间内恢复堆序。qp[]数组是让decreaseKey从 O(V) 降到 O(log V) 的关键物理结构。4. 第37页表格的物理含义表格列出了不同优先队列实现下Dijkstra 算法执行V次insert、V次delete-min、E次decrease-key的总代价实现insertdelete-mindecrease-key总时间无序数组1V1O(V²)二叉堆log Vlog Vlog VO(E log V)d 叉堆log_d Vd log_d Vlog_d VO(E log_{d} V)斐波那契堆1摊还log V摊还1摊还O(E V log V)逐个解释无序数组insert是 O(1)直接放末尾decreaseKey是 O(1)直接改那个槽位但delete-min需要扫描整个数组找最小值O(V)。总时间 O(V²)。适合稠密图E ≈ V²此时 V² E log V。二叉堆三个操作都是 O(log V)。insert和decreaseKey都需要swimdelete-min需要sink。总时间 O(E log V)。这是实际中最常用的方案。d 叉堆每个节点有 d 个子节点。insert和decreaseKey是 O(log_d V)树更矮但delete-min需要在 d 个子节点中找最小的是 O(d log_d V)。对于特定 d如 d4实测比二叉堆快。斐波那契堆insert和decreaseKey是摊还 O(1)delete-min是摊还 O(log V)。理论最优但常数因子大、实现复杂实际中很少用。5. 与 Prim 算法的关系Prim 算法的IndexMinPQ用法与 Dijkstra 几乎相同区别只在键值的物理含义Dijkstra 的键值从源点 s 到顶点的累计路径长度。Prim 的键值顶点到树 T 的最小单条边权重。decreaseKey在两者中的作用相同当发现一条更优的连接时更新顶点在优先队列中的键值使其在堆中上浮。一句话总结decreaseKey是索引优先队列提供的操作它允许你在 O(log V) 时间内修改一个已存在顶点的键值并恢复堆序。它避免了懒惰版本中堆规模膨胀到 O(E) 的问题使 Dijkstra 和 Prim 的时间复杂度达到 O(E log V)。实现它的物理关键是qp[]反向索引数组让你能 O(1) 找到顶点在堆中的位置。Q稍等我忽然回味过来很奇怪的一点。算法的时间复杂度不应该是所有代码加起来的结果吗就算是取大头似乎也应该是找循环这一类的代码。但长久以来我们计算时间复杂度都是取它数据结构层面的操作来计算具体来说就是它在内存中如何被存储我们在这种存储结构进行操作的次数。例如对于dijkstra算法每个层面的点都会对其所连接的点进行松弛那么松弛的复杂度必然不是V因为会有重复。似乎是E没错正是如此松弛的关键是对于每个e.weight我们都会进行松弛计算这恰好就是decrease key的复杂度。这是巧合还是一种必然A这不是巧合而是成本模型cost model选择的必然结果。为什么时间复杂度不是“所有代码行数相加”因为在一段代码中不同操作的物理代价差异巨大。在 Dijkstra 的relax方法中javaif (distTo[w] distTo[v] e.weight()) { distTo[w] distTo[v] e.weight(); // 数组写入O(1) edgeTo[w] e; // 数组写入O(1) if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); // 堆操作O(log V) else pq.insert(w, distTo[w]); // 堆操作O(log V) }数组读写访问内存中的连续槽位常数时间。堆操作decreaseKey、insert涉及指针跳转、比较、交换时间与堆的深度成正比。如果你把所有代码行数加起来你会得到类似E * (常数 堆操作代价)的结果。但E * 常数这一项数组读写在E * log V面前可以忽略。所以时间复杂度只保留主导项。为什么“松弛次数 E”直接映射到“decreaseKey 次数 E”这不是巧合而是因为松弛动作的触发条件与 decreaseKey 的触发条件在物理上是一一对应的。物理时序每个顶点 v 从优先队列取出一次然后遍历adj[v]。adj[v]中有outdegree(v)条边。对每条边 e v→w执行一次relax(e)。如果relax成功更新了distTo[w]则如果 w 还在堆里调用decreaseKey。如果 w 不在堆里调用insert。所以松弛的总次数 所有顶点的出度之和 E。堆操作的总次数≤ E因为有些松弛可能不更新 distTo不触发堆操作。E 次松弛是物理动作的直接计数E 次堆操作是这些松弛中实际触发更新的子集。在分析时间复杂度时我们用 E 作为堆操作的上界因为即使不是每次松弛都触发堆操作E 也是渐近紧确的。为什么我们选择“堆操作次数”作为成本模型因为堆操作是物理上最昂贵的动作。在 Dijkstra 中数组读写O(1) 每条边总计 O(E)。比较操作O(1) 每条边总计 O(E)。堆操作O(log V) 每条边总计 O(E log V)。当 V 和 E 都很大时E log V远大于E。所以总时间由堆操作主导。我们只需要计算堆操作的次数就能得到时间复杂度的渐近表达式。这是算法分析的通用方法选择一个“主导操作”计算它被执行的次数。排序算法中主导操作是比较和交换Dijkstra 中主导操作是优先队列操作Kruskal 中主导操作是并查集的find和union。回到你的问题“松弛的关键是对于每个 e.weight 我们都会进行松弛计算这恰好就是 decrease key 的复杂度。这是巧合还是一种必然”必然。因为松弛动作是遍历adj[v]时对每条出边执行的。所有顶点的出度之和是 E。而每次松弛如果成功更新 distTo[w]就会触发一次堆操作。所以堆操作的次数由 E 决定这不是巧合而是算法物理结构遍历邻接表决定的。你计算的是“松弛次数”我们把它等价为“堆操作次数”因为松弛次数 E。堆操作次数 ≤ E且在最坏情况下 E。堆操作的代价log V远大于松弛本身的开销O(1)。所以你实际上是在计算主导操作的次数而这正是时间复杂度分析的正确做法。你自发的直觉和分析方法是一致的。Q那么根据以往的分析经验还可以发现在数据类型下对于数据的操作各种查找、读写往往是最昂贵的。A观察方向是对的但需要把“对数据的操作”这句话精确化。不是所有对数据的操作都昂贵而是“在动态数据结构中为了维持结构不变量而执行的操作”最昂贵。1. 连续内存的直接访问数组索引——最便宜物理动作a[i] value。CPU 执行的是基地址 i * 元素大小的地址计算然后直接读写内存。代价O(1)。没有指针跳转没有缓存缺失因为数组是连续内存命中率高。在 Dijkstra 中distTo[w] ...和edgeTo[w] e就是这种操作每条边一次总计 O(E)。它虽然次数多但单次极快所以不构成瓶颈。2. 顺序扫描遍历链表、数组——中等物理动作沿着指针或索引逐个访问节点。代价O(N)。每次访问都有指针跳转链表或索引递增数组。链表的指针跳转会导致 CPU 缓存缺失cache miss因为节点在堆上分散分布。在 Kruskal 中并查集的find沿parent[]数组向上跳这个跳转次数虽然接近常数路径压缩后但它是“跳着走”的不是连续扫描。它的代价比 O(1) 大但比 O(N) 小。3. 维护结构不变量的操作堆的 swim/sink、树的旋转、哈希表的扩容——最昂贵物理动作堆的swim比较节点与父节点如果违反堆序父键 子键交换它们。每次交换涉及两个数组槽位的读写和一次比较。跳转次数等于树高log V。树的旋转修改多个指针左旋、右旋、颜色翻转涉及 5~6 次指针赋值。哈希表扩容重新计算所有键的哈希重新分配内存把元素搬到新桶。代价O(log N) 或 O(N)。贵在它的单次操作不是一次内存访问而是一连串依赖前一步结果的指针操作。你无法预知下一次访问哪个地址指针跳转所以 CPU 无法提前预取数据预取失效每次跳转都可能触发缓存缺失。为什么 Dijkstra 的时间复杂度由堆操作决定因为 Dijkstra 的物理动作中数组读写distTo、edgeTo是第 1 类单次 O(1)总 O(E)。堆操作insert、decreaseKey、delMin是第 3 类单次 O(log V)总 O(E log V)。第 3 类的单次代价本身就比第 1 类大一个 log V 的因子。即使第 1 类的次数也是 E它的总代价也远小于第 3 类。所以分析时只需要计算第 3 类的次数。你“对数据的操作往往最昂贵”的直觉在 EDA 中的物理对应在 EDA 工具中网表netlist存储为数组或哈希表。按索引访问gate[i]是第 1 类便宜。时序图timing graph用邻接表存储遍历它涉及指针跳转是第 2 类。优先队列用于静态时序分析中的关键路径计算涉及swim/sink是第 3 类昂贵。所以 EDA 工程师在设计数据结构时会尽量减少第 3 类操作的次数。比如用桶排序bucket sort代替堆来管理时序事件把 O(log V) 降到 O(1)。总结你的观察“对数据的操作往往最昂贵”需要修正为在动态数据结构中为维护结构不变量而执行的指针操作swim/sink/旋转/扩容是最昂贵的。数组索引读写很便宜顺序扫描中等结构维护操作昂贵。时间复杂度分析的本质就是找出代码中执行次数最多的那类最昂贵的操作并计算它的总次数。Q为什么说这是为了维护结构不变量这里不变的是什么其结构吗可按照语法来读不变的是量。量是可以修改的怎么会不变A在算法和数据结构中“不变量”指的不是“值不变”而是“某种条件约束必须始终成立”。它是一个逻辑命题不是一个数值。用堆来具体说明二叉堆的结构不变量是对任意节点 k父节点 k/2 的键值 ≤ 节点 k 的键值最小堆。这个命题的状态有两种成立或不成立。当你执行insert把新元素放到数组末尾时这个新元素可能比它的父节点小不变量被破坏。然后你执行swim比较新元素和父节点如果父节点更大交换它们。交换后再比较新的父节点。重复直到父节点 ≤ 当前节点或者到达根。当swim结束时不变量重新成立。所以swim的物理目的就是修复被破坏的不变量。它修改的是具体数值交换数组槽位的内容但它维护的是“父 ≤ 子”这个逻辑条件。为什么叫“不变”量因为这个条件必须在每一次操作完成之后都成立。你可以在操作过程中临时破坏它insert时新元素可能比父小。但操作结束时它必须恢复为真。它对所有节点、所有时刻都必须成立只要数据结构处于“合法”状态。“不变”指的是这个条件在操作的边界上保持不变始终为真而不是说数值不能变。对比没有不变量的数据结构一个无序数组。你add一个元素直接放到末尾。没有任何条件需要维护。add操作结束后不需要修复任何东西。这就是为什么无序数组的add是 O(1)——它没有不变量不需要做任何结构维护。而堆的insert是 O(log V)——它必须执行swim来修复不变量。回到你的问题“不变的是量。量是可以修改的怎么会不变”不变的不是数值是“父键 ≤ 子键”这个逻辑关系。数值可以修改交换但修改之后逻辑关系必须恢复为真。算法操作的过程就是不断破坏和修复这个逻辑关系的过程。在 EDA 中也有类似的例子时钟树的不变量是“所有触发器的时钟到达时间之差不超过某个阈值”。你可以在综合和布局过程中暂时违反它但最终签核时这个条件必须成立。不变量是一种约束不是数值。