概述
单源最短路径问题(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]。
![](https://img.ultipa.cn/draw/draw_5efe262b9d55403bb207d91f98978610.jpg?v='1690868991937')
2. 在每次迭代中,从第一个非空桶B[i]中移除所有节点:
- 松弛所有被移除节点的轻边邻居,被松弛的节点可能被分配到B[i]或B[i+1]桶;推迟对重边邻居的松弛。
- 如果B[i]中又有节点加入,重复上述操作直到B[i]为空。
- 松弛所有推迟的重边邻居。
![](https://img.ultipa.cn/draw/draw_d6aa4c182255474c9fc3a7497026cadd.jpg?v='1689214052735')
松弛轻边邻居a为dist(a) = min(0+2,∞) = 2,d为dist(b) = min(0+3,∞) = 3
![](https://img.ultipa.cn/draw/draw_4621a1562f9c4a39b8baa59c1473e65a.jpg?v='1689214040424')
轻边邻居b无法被松弛
松弛重边邻居c为 dist(c) = min(0+5,∞) = 5,d无法被松弛
3. 重复第2步,直到所有桶为空。
![](https://img.ultipa.cn/draw/draw_d5e799ee7a6d49c092985cbfdec248d1.jpg?v='1689214188453')
松弛轻边邻居g为dist(g) = min(5+2,∞) = 7,b、c和d无法被松弛
松弛重边邻居e为dist(e) = min(5+4,∞) = 9,a和b无法被松弛
![](https://img.ultipa.cn/draw/draw_2bf5a342706b466caa35c251dac05881.jpg?v='1689214248468')
轻边邻居c无法被松弛
松弛重边邻居f为dist(f) = min(7+5,∞) = 12
![](https://img.ultipa.cn/draw/draw_ce6687f10f154b228eed39d760afd1f2.jpg?v='1689214310161')
松弛轻边邻居f为dist(f) = min(9+1,12) = 10
![](https://img.ultipa.cn/draw/draw_0c6f83a20c18478e86b1145df27561cd.jpg?v='1689214362303')
轻边邻居e无法被松弛
重边邻居g无法被松弛
所有桶为空,算法结束
通过将节点放入不同的桶进行并行处理,Delta-Stepping算法可以更有效地利用可用的计算资源,适用于大规模图和并行计算环境。
特殊说明
- Delta-Stepping单源最短路径算法适用于具有非负边权重的图。如果存在负权重,Delta-Stepping单源最短路径算法输出的结果也许是不正确的。这种情况建议使用SPFA算法。
- 如果两个节点之间存在多条最短路径,算法会找出所有这些路径。
- 在非连通图中,算法只输出源节点所在的连通分量内所有节点到源节点的最短距离。
语法
- 命令:
algo(sssp)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | _id / _uuid |
/ | / | 否 | 单个源节点的ID/UUID |
direction | string | in , out |
/ | 是 | 最短路径的方向,忽略则不考虑方向 |
edge_schema_property | []@schema?.property |
数值类型,需LTE | / | 是 | 用作边权重的边属性,权重值为所有指定属性值的和;忽略则不考虑权重 |
record_path | int | 0 , 1 |
0 |
是 | 1 代表返回最短路径,0 代表返回最短距离 |
sssp_type | string | delta_stepping |
dijkstra |
是 | 计算增量步进单源最短路径时,保持此项为delta_stepping |
delta | float | >0 | 2 |
是 | 增量(delta)的值 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
order | string | asc , desc |
/ | 是 | 按最短距离大小对结果进行排序 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_a491e2167bcc45ae9b56d15f1625cd49.jpg?v='1691401614194')
文件回写
配置项 | record_path |
回写内容 | 描述 |
---|---|---|---|
filename | 0 | _id ,totalCost |
从源节点到每个其他节点的最短距离/成本 |
1 | _id --_uuid --_id |
从源节点到每个其他节点的最短路径,由构成路径的节点ID和边UUID交替出现表示 |
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
直接返回
别名序号 | record_path |
类型 | 描述 | 列名 |
---|---|---|---|---|
0 | 0 | []perNode | 从源节点到每个其他节点的最短距离/成本 | _uuid , totalCost |
1 | []perPath | 从源节点到每个其他节点的最短路径,由构成路径的节点和边的UUID交替出现表示 | / |
algo(sssp).params({
uuids: 1,
edge_schema_property: '@default.value',
sssp_type: 'delta_stepping',
delta: 2,
order: 'desc'
}) as costs
return costs
结果:costs
_uuid | totalCost |
---|---|
7 | 8 |
5 | 5 |
4 | 5 |
3 | 5 |
6 | 4 |
2 | 2 |
1 | 0 |
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
1 |
1--[101]--2 |
1--[102]--6 |
1--[102]--6--[107]--5 |
1--[101]--2--[105]--4 |
1--[101]--2--[104]--3 |
1--[102]--6--[107]--5--[109]--7 |
流式返回
别名序号 | record_path |
类型 | 描述 | 列名 |
---|---|---|---|---|
0 | 0 | []perNode | 从源节点到每个其他节点的最短距离/成本 | _uuid , totalCost |
1 | []perPath | 从源节点到每个其他节点的最短路径,由构成路径的节点和边的UUID交替出现表示 | / |
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
_uuid | totalCost |
---|---|
6 | 4 |
2 | 2 |
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
1--[102]--6--[107]--5 |
1--[101]--2--[105]--4 |
1--[101]--2--[104]--3 |
1--[102]--6 |
1--[101]--2 |