增量步长单源最短路径

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法以类似的方式对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法以类似的方式对待所有选定的关系，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，丢弃任何关系权重的值。

简介

增量步长最短路径算法计算图中源节点到所有可到达节点的所有最短路径。该算法支持具有正关系权重的加权图。要计算源节点和单个目标节点之间的最短路径，可以使用 Dijkstra 源-目标。

与 Dijkstra 单源算法不同，Delta-Stepping 算法是一种距离校正算法。这种特性允许它并行遍历图。该算法保证始终找到源节点和目标节点之间的最短路径。但是，如果两个节点之间存在多个最短路径，则该算法不能保证每次计算都返回相同的路径。

GDS 实现基于 [1]，并结合了 [2] 中讨论的桶融合优化。算法实现使用多个线程执行，可以在过程配置中定义。

有关此算法的更多信息，请参见

语法

本节介绍了在每种执行模式下执行 Delta-Stepping 算法时使用的语法。我们正在描述命名的图变体语法。要了解有关一般语法变体的更多信息，请参见语法概述。

每个模式的 Delta-Stepping 语法

在命名图上以流模式运行 Delta-Stepping。

CALL gds.allShortestPaths.delta.stream(
  graphName: String,
  configuration: Map
)
YIELD
  index: Integer,
  sourceNode: Integer,
  targetNode: Integer,
  totalCost: Float,
  nodeIds: List of Integer,
  costs: List of Float,
  path: Path

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定内容和/或图过滤的配置。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可以提供的 ID，便于跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
delta	浮点数	`2.0`	是	用于对具有相同暂定距离到源节点的节点进行分组的桶宽度。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

表 3. 结果
名称	类型	描述
index	整数	找到路径的 0 基索引。
sourceNode	整数	路径的源节点。
targetNode	整数	路径的目标节点。
totalCost	浮点数	从源到目标的总成本。
nodeIds	整数列表	路径上按遍历顺序排列的节点 ID。
costs	浮点数列表	路径上每个节点的累积成本。
path	路径	表示为 Cypher 实体的路径。

mutate 模式在投影图中创建新的关系。每个关系代表从源节点到目标节点的路径。路径的总成本通过 totalCost 关系属性存储。

在命名图上以 mutate 模式运行 Delta-Stepping。

CALL gds.allShortestPaths.delta.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  configuration: Map

表 4. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定内容和/或图过滤的配置。

表 5. 配置
名称	类型	默认值	可选	描述
mutateRelationshipType	字符串	`n/a`	否	用于写入投影图的新关系的关系类型。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可以提供的 ID，便于跟踪算法的进度。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
delta	浮点数	`2.0`	是	用于对具有相同暂定距离到源节点的节点进行分组的桶宽度。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
mutateMillis	整数	将关系添加到投影图中的毫秒数。
relationshipsWritten	整数	添加的关系数。
configuration	映射	用于运行算法的配置。

write 模式在 Neo4j 数据库中创建新的关系。每个关系代表从源节点到目标节点的路径。使用关系属性存储其他路径信息。默认情况下，write 模式存储 totalCost 属性。可选地，您还可以存储路径上中间节点的 nodeIds 和 costs。

在命名图上以 write 模式运行 Delta-Stepping。

CALL gds.allShortestPaths.delta.write(
  graphName: String,
  configuration: Map
)
YIELD
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  configuration: Map

表 7. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定内容和/或图过滤的配置。

表 8. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可以提供的 ID，便于跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`n/a`	否	用于将计算出的关系持久化到 Neo4j 数据库中的关系类型。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
delta	浮点数	`2.0`	是	用于对具有相同暂定距离到源节点的节点进行分组的桶宽度。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
writeNodeIds	布尔值	`假`	是	如果为真，则写入的关系具有 nodeIds 列表属性。
writeCosts	布尔值	`假`	是	如果为真，则写入的关系具有 costs 列表属性。

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
writeMillis	整数	将关系写入 Neo4j 的毫秒数。
relationshipsWritten	整数	写入的关系数。
configuration	映射	用于运行算法的配置。

在命名图上以 stats 模式运行 Delta-Stepping。

CALL gds.allShortestPaths.delta.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

表 10. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定内容和/或图过滤的配置。

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可以提供的 ID，便于跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
delta	浮点数	`2.0`	是	用于对具有相同暂定距离到源节点的节点进行分组的桶宽度。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
configuration	映射	用于运行算法的配置。

Delta

delta 参数定义一个范围，用于对具有相同暂定距离到起始节点的节点进行分组。这些范围也称为桶。在算法的每次迭代中，将并行处理具有最小暂定距离的非空桶。delta 参数是该算法的主要调整旋钮，它控制可以并行处理的工作负载。通常，对于幂律图，其中许多节点可以在几跳内到达，建议使用较小的 delta（例如 2）。对于高直径图，例如运输网络，建议使用较高的 delta 值（例如 10000）。请注意，该值可能会根据图拓扑和关系属性的值范围而异。

示例

以下所有示例都应在空数据库中运行。

这些示例使用 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行 Delta-Stepping 算法的示例。目的是说明结果的外观，并提供在实际设置中如何使用该算法的指南。我们将在一个小的交通网络图上执行此操作，该图包含少量节点并以特定模式连接在一起。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE (a:Location {name: 'A'}),
       (b:Location {name: 'B'}),
       (c:Location {name: 'C'}),
       (d:Location {name: 'D'}),
       (e:Location {name: 'E'}),
       (f:Location {name: 'F'}),
       (a)-[:ROAD {cost: 50}]->(b),
       (a)-[:ROAD {cost: 50}]->(c),
       (a)-[:ROAD {cost: 100}]->(d),
       (b)-[:ROAD {cost: 40}]->(d),
       (c)-[:ROAD {cost: 40}]->(d),
       (c)-[:ROAD {cost: 80}]->(e),
       (d)-[:ROAD {cost: 30}]->(e),
       (d)-[:ROAD {cost: 80}]->(f),
       (e)-[:ROAD {cost: 40}]->(f);

此图构建了一个具有位置之间道路的交通网络。与现实世界一样，图中的道路具有不同的长度。这些长度由 cost 关系属性表示。

以下语句将使用 Cypher 投影投影图，并将图存储在图目录中，名称为 'myGraph'。

MATCH (source:Location)-[r:ROAD]->(target:Location)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .cost } }
)

在以下示例中，我们将演示使用此图的 Delta-Stepping 最短路径算法。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以使用任何执行模式完成。在本示例中，我们将使用 write 模式。估算算法有助于了解在您的图上运行算法将产生的内存影响。当您稍后在其中一种执行模式下实际运行算法时，系统将执行估算。如果估算表明执行很有可能超过其内存限制，则将禁止执行。要详细了解这一点，请参见自动估算和执行阻止。

有关 estimate 的更多信息，请参见内存估算。

以下内容将估算在 write 模式下运行算法所需的内存。

MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.delta.write.estimate('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'PATH'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	9	368	576	"[368 字节 ... 576 字节]"

流

在 stream 执行模式下，算法返回每对源-目标的的最短路径。这使我们可以直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。

有关 stream 模式的更多信息，请参见流。

以下内容将运行算法并流式传输结果

MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.delta.stream('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    delta: 3.0
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNodeName,
    gds.util.asNode(targetNode).name AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(path) as path
ORDER BY index

表 14. 结果
index	sourceNodeName	targetNodeName	totalCost	nodeNames	costs	path
0	"A"	"A"	0.0	["A"]	[0.0]	[Node[0]]
1	"A"	"B"	50.0	["A", "B"]	[0.0, 50.0]	[Node[0], Node[1]]
2	"A"	"C"	50.0	["A", "C"]	[0.0, 50.0]	[Node[0], Node[2]]
3	"A"	"D"	90.0	["A", "B", "D"]	[0.0, 50.0, 90.0]	[Node[0], Node[1], Node[3]]
4	"A"	"E"	120.0	["A", "B", "D", "E"]	[0.0, 50.0, 90.0, 120.0]	[Node[0], Node[1], Node[3], Node[4]]
5	"A"	"F"	160.0	["A", "B", "D", "E", "F"]	[0.0, 50.0, 90.0, 120.0, 160.0]	[Node[0], Node[1], Node[3], Node[4], Node[5]]

结果显示了节点 A 与图中所有其他可达节点之间的最短路径的总成本。它还显示了为查找最短路径而遍历的节点 ID 的有序列表，以及访问节点的累积成本。这可以在示例图中验证。Cypher 路径对象可以通过 path 返回字段返回。路径对象包含节点对象和具有 cost 属性的虚拟关系。

Mutate

mutate 执行模式使用新关系更新命名图。每个新关系代表从源节点到目标节点的路径。关系类型使用 mutateRelationshipType 选项配置。总路径成本使用 totalCost 属性存储。

当多个算法一起使用时，mutate 模式特别有用。

有关 mutate 模式的更多信息，请参见 Mutate。

以下内容将在 mutate 模式下运行算法

MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.delta.mutate('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    mutateRelationshipType: 'PATH'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 15. 结果
relationshipsWritten
6

执行上述查询后，内存中图将使用类型为 PATH 的新关系更新。新关系将存储单个属性 totalCost。

生成的關係總是定向的，即使輸入圖是非定向的。

写入

write 执行模式使用新关系更新 Neo4j 数据库。每个新关系代表从源节点到目标节点的路径。关系类型使用 writeRelationshipType 选项配置。总路径成本使用 totalCost 属性存储。中间节点 ID 使用 nodeIds 属性存储。到达中间节点的累积成本使用 costs 属性存储。

有关 write 模式的更多信息，请参见写入。

以下内容将在 write 模式下运行算法

MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.delta.write('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'PATH',
    writeNodeIds: true,
    writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 16. 结果
relationshipsWritten
6

上述查询将 6 个类型为 PATH 的关系写回 Neo4j。这些关系存储三个描述路径的属性：totalCost、nodeIds 和 costs。

写入的关系总是定向的，即使输入图是非定向的。