while 存在非空桶 do
    令 i 为当前最小索引的非空桶。
    重复处理当前桶 B[i]，直到它变为空。

并行与分布式系统中的并行单源最短路径：基于优先队列的并行Dijkstra算法的延迟更新与多桶优化（Δ-Stepping 的变体） 在并行与分布式系统中，求解大规模稀疏图中的单源最短路径（Single-Source Shortest Paths, SSSP）是一个基础且重要的问题。传统的Dijkstra算法因其严格的全局优先级队列顺序，难以有效并行化。一种高效且被广泛研究的并行化思路是 放松处理的严格顺序 ，允许“近似”地按距离顺序处理顶点，从而暴露更多并行性。 基于Δ-Stepping的变体算法 是其中的杰出代表，它通过引入“桶”来对距离值进行分组，并延迟处理距离更新，极大地提高了并行效率。 我将循序渐进地为你讲解这个算法的核心思想、步骤和细节。 1. 问题描述 给定一个 加权有向图 \( G=(V, E) \)，其中每条边 \( e \in E \) 有一个非负的权重 \( w(e) \)。给定一个 源顶点 \( s \in V \)。目标是计算出从源点 \( s \) 到图中所有其他顶点 \( v \in V \) 的 最短路径距离 \( dist[ v] \)。在并行计算环境中（例如共享内存的多核系统），我们希望利用多个处理器核心， 加速 最短路径的计算过程。 核心挑战 ：经典的Dijkstra算法维护一个全局优先队列，每次取出距离最小的顶点进行处理。这个“取最小”操作是严格的串行瓶颈，因为必须等到当前最小顶点处理完毕后，才能确定下一个最小顶点，这使得直接的并行化效率低下。 2. 算法核心思想：放松与桶分组 该算法的核心是 Δ-Stepping思想 的一个高效实现变体。基本策略是： 分组 ：将可能的最短路径距离范围划分为一系列连续的“桶”（buckets），每个桶覆盖一个长度为 \( \Delta \) 的距离区间。例如，桶 \( B[ i] \) 包含所有满足 \( i\Delta \leq dist[ v] < (i+1)\Delta \) 的顶点 \( v \)。 延迟更新 ：算法不再严格地每次只处理一个全局距离最小的顶点，而是每次处理 一个桶中的所有顶点 。在处理一个桶时，可能会发现一些顶点的距离可以更小，从而被“重新插入”到当前桶或更早的桶中。 并行处理 ：在一个桶内部，顶点之间的松弛操作是 相互独立 的，因此可以高度并行化。 关键参数 ：\( \Delta \)。如果 \( \Delta \) 太小，算法退化为类似Dijkstra的串行行为；如果 \( \Delta \) 太大，则退化为类似Bellman-Ford的行为，并行度高但迭代轮次多。通常 \( \Delta \) 设置为图中边权重的平均值或中位数。 3. 算法步骤详解 让我们一步步拆解这个并行SSSP算法的执行过程。 步骤0：初始化 为每个顶点 \( v \) 维护一个距离估计 \( dist[ v ] \)： \( dist[ s ] = 0 \) \( \forall v \neq s, dist[ v ] = \infty \) 根据参数 \( \Delta \) 创建一组“桶” \( B[ 0], B[ 1], B[ 2 ], ... \)。通常用动态数组（如向量）或链表实现。 将源点 \( s \) 插入到桶 \( B[ 0] \) 中（因为 \( 0 \leq dist[ s] < \Delta \)）。 维护一个指针 \( idx \)，表示当前正在处理的桶的索引，初始化为 0。 步骤1：主循环（处理各个桶） 算法在 while 循环中运行，直到所有桶为空。 步骤2：处理单个桶 B[ i] 这是算法的核心，分为两个阶段，目的是安全地松弛当前桶中顶点发出的“轻边”和“重边”。 定义 ： 轻边 ：权重 \( w \leq \Delta \) 的边。 重边 ：权重 \( w > \Delta \) 的边。 阶段1：松弛轻边 并行地处理当前桶 \( B[ i] \) 中的 所有顶点 。 对每个顶点 \( u \in B[ i] \)，并行地对其每条出边 \( (u, v) \) 进行 轻边松弛 ： 如果 \( w(u, v) \leq \Delta \)： 计算新的候选距离： new_dist = dist[u] + w(u, v) 。 如果 new_dist < dist[v] ： 原子性地更新 dist[v] = new_dist 。 根据新的 dist[v] 计算其应属的桶索引 j = floor(dist[v] / \Delta) 。 将顶点 \( v \) 从它原来所在的桶（如果存在）中移除，并插入到桶 \( B[ j ] \) 中。这个过程需要并发控制（如锁或原子操作）。 为什么先处理轻边 ？因为从当前桶（距离在 \( [ i\Delta, (i+1)\Delta) \) 内）出发，经过一条轻边到达的顶点，其距离仍有可能落在 当前桶 \( B[ i] \) 或更早的桶 中。如果不先处理完这些轻边，就移除当前桶的顶点，可能会导致后续插入的顶点被重复处理，但更重要的是，这保证了算法能按照距离不减少的顺序进行近似处理，是正确性的关键。 阶段2：松弛重边并确认当前桶顶点 在阶段1之后，再次并行处理当前桶 \( B[ i] \) 中 剩余的顶点 （注意，阶段1的操作可能将一些顶点重新插入到 \( B[ i ] \) 中，也可能将一些顶点移动到其他桶）。 对每个顶点 \( u \in B[ i] \)，并行地对其每条出边 \( (u, v) \) 进行 重边松弛 ： 如果 \( w(u, v) > \Delta \)： 计算 new_dist = dist[u] + w(u, v) 。 如果 new_dist < dist[v] ： 原子性更新 dist[v] = new_dist 。 计算桶索引 j = floor(dist[v] / \Delta) 。 将 \( v \) 移动到桶 \( B[ j ] \)。 在此阶段之后，桶 \( B[ i] \) 中所有顶点的距离都已被“确认”（即不可能再被来自更早距离顶点的边松弛得更小），可以安全地将整个桶 \( B[ i ] \) 清空。实际上，随着阶段2的进行，顶点会被移出，处理完毕后该桶自然为空。 移动到下一个桶 ： 将当前桶索引 \( i \) 递增，寻找下一个非空桶，重复步骤2。 4. 算法正确性直观解释 这个算法的正确性基于Dijkstra算法的核心思想： 当一个顶点的最短距离被最终确定时，所有距离更小的顶点都已经被处理过了 。 在我们的算法中，一个顶点的距离在它 最后一次从某个桶中被移除（即，在阶段2中被处理）时 被“确认”。 通过 先处理所有轻边 ，我们确保了：如果一个顶点的最短路径可以通过一条轻边从当前桶的某个顶点到达，那么它一定会在当前桶被清空前被重新插入并处理。这保证了处理顺序是“近似非递减”的。 重边由于权重较大，从当前桶出发经过重边到达的顶点，其距离必然落入 更晚的桶 （索引 \( j > i \)），因此可以在后续轮次中安全处理，不会影响当前桶内顶点距离的最终性。 5. 并行性分析 桶内并行 ：在“松弛轻边”和“松弛重边”两个阶段中，对桶内所有顶点的出边进行松弛操作是 完全独立 的，可以并行执行。这是算法并行度的主要来源。 桶间顺序 ：桶的处理顺序仍然是串行的（从索引小的桶到索引大的桶）。但由于每个桶内通常包含许多顶点，只要桶足够“满”，就能有效利用并行资源。 并发控制 ：当多个线程同时尝试更新同一个顶点 \( v \) 的距离，并将其插入/移动到某个桶时，需要使用 锁 （对每个顶点或每个桶加锁）或 无锁编程 技术（如CAS原子操作）来保证数据一致性。 6. 参数选择与性能 Δ的选择 ：这是性能和并行度的权衡旋钮。 较小的 Δ：桶更多，每个桶内顶点数较少，更接近串行Dijkstra，顺序性强，并行度低，但总轮次（桶处理次数）可能较少。 较大的 Δ：桶更少，每个桶内顶点数极多，并行度高，但可能一个顶点会被多次插入/移出同一个桶（类似于Bellman-Ford的冗余松弛），增加总工作量。 实践中，常设置 \( \Delta = \frac{\text{平均边权重}}{2} \) 或通过实验调优。 适用于 ：大规模 稀疏图 ，且边权重非负。对于稠密图或存在负权边的图，此算法不适用。 总结 这个基于 Δ-Stepping 思想的并行单源最短路径算法，通过 用桶分组替代严格的全局优先队列 ，并巧妙地 分两阶段（先轻边后重边）处理每个桶 ，在保证算法正确性的前提下， 将大量的边松弛操作暴露为可并行执行的任务 。它成功地将一个固有的串行算法（Dijkstra）转化为一个高效的并行算法，是大规模图处理系统中的关键技术之一。其核心在于 以可控的、近似的顺序性为代价，换取大量的并行计算机会 。