概述

单源最短路径问题（Single-Source Shortest Path, SSSP）计算的是从图中一个源节点到其余所有可达节点的最短路径。最短路径是指全部可能的路径中，所有边的权重和最小的路径；在无权图的情况下，是指边的数量最少的路径。最短路径的成本（或距离）是指所有边的权重和或数量。

Delta-Stepping（增量步进）单源最短路径算法可以看成是 Dijkstra算法的一种变体，具有并行计算的潜力。

算法的相关资料如下：

• U. Meyer, P.Sanders, Δ-Stepping: A Parallel Single Source Shortest Path Algorithm (1998)

基本概念

Delta-Stepping单源最短路径

Delta-Stepping单源最短路径算法引入了“桶”（Bucket）的概念，并且以一种更粗粒度的方式执行松弛操作。该算法利用一个增量参数delta (Δ) > 0来实现以下目标：

• 维护一个数组B，其中B[i]包含距离在范围[iΔ, (i+1)Δ)内的节点。因此，Δ也被称为“步长”或“桶宽”。
• 区分图中权重≤Δ的“轻边”（Light Edges）和权重>Δ的“重边”（Heavy Edges）。在松弛过程中，优先考虑轻边节点，因为它们的权重更低，更有可能产生较短的路径。

松弛操作是指通过考虑经过节点u的路径，更新与节点u相连的节点v的距离，使其获得可能的更短距离。具体来说，节点v的距离会被更新为dist(v) = dist(u) + w(u,v)，其中w(u,v)是边(u,v)的权重。此更新仅在当前dist(v)大于dist(u) + w(u,v)时进行。

在Delta-Stepping单源最短路径算法中，松弛操作还包括根据更新后的距离值将被松弛的节点分配到相应的桶中。

我们将通过计算示例图中以b为源节点的无向加权最短路径来解释Delta-Stepping单源最短路径算法的基本实现，设置Δ为3：

1. 算法开始时，所有节点的距离都被设为无穷大，除了源节点，它的距离被设为0。将源节点分配到桶B[0]。

2. 在每次迭代中，从第一个非空桶B[i]中移除所有节点：

• 松弛所有被移除节点的轻边邻居，被松弛的节点可能被分配到B[i]或B[i+1]桶；推迟对重边邻居的松弛。
• 如果B[i]中又有节点加入，重复上述操作直到B[i]为空。
• 松弛所有推迟的重边邻居。

3. 重复第2步，直到所有桶为空。

通过将节点放入不同的桶进行并行处理，Delta-Stepping算法可以更有效地利用可用的计算资源，适用于大规模图和并行计算环境。

特殊说明

• Delta-Stepping单源最短路径算法适用于具有非负边权重的图。如果存在负权重，Delta-Stepping单源最短路径算法输出的结果也许是不正确的。这种情况建议使用SPFA算法。
• 如果两个节点之间存在多条最短路径，算法会找出所有这些路径。
• 在非连通图中，算法只输出源节点所在的连通分量内所有节点到源节点的最短距离。

语法

• 命令：algo(sssp)
• 参数：

示例

示例图如下：

文件回写

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'delta_stepping',
  delta: 2
}).write({
  file: {
    filename: 'costs'
  }
})

结果：文件costs

G,8
F,4
E,5
D,5
C,5
B,2
A,0

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'delta_stepping',
  delta: 2,
  record_path: 1
}).write({
  file: {
    filename: 'paths'
  }
})

结果：文件paths

A--[102]--F--[107]--E--[109]--G
A--[102]--F--[107]--E
A--[101]--B--[105]--D
A--[101]--B--[104]--C
A--[102]--F
A--[101]--B
A

直接返回

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'delta_stepping',
  delta: 2,
  order: 'desc'
}) as costs
return costs

结果：costs

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  direction: 'out',
  record_path: 1,
  sssp_type: 'delta_stepping',
  delta: 2,
  order: 'asc'
}) as paths
return paths

结果：paths

流式返回

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'delta_stepping'
}).stream() as costs
where costs.totalCost <> [0,5]
return costs

结果：costs

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'delta_stepping',
  record_path: 1
}).stream() as p
where length(p) <> [0,3]
return p

结果：p