✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

单源最短路径问题（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_tyle: '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_tyle: '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_tyle: '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_tyle: '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