Bellman-Ford 单源最短路径

有向

无向

异构节点

异构关系

加权关系

术语表

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

简介

Bellman-Ford 路径算法计算节点之间的最短路径。

与只适用于非负关系权重的图的 Dijkstra 算法不同，Bellman-Ford 算法也能处理带负权重的图，前提是源节点无法到达任何涉及负环的节点。图中的环是起始和结束于同一节点的路径。负环是关系权重总和为负的环。当存在负环时，最短路径不容易定义。这是因为我们可以多次遍历负环，每次都能获得越来越小的成本。

当 Bellman-Ford 算法检测到负环时，它将尝试返回负环而不是最短路径。请注意，在某些情况下，由于修改算法以支持并行实现，该实现可能无法枚举它们。

由于负环的完整集合可能太大而无法枚举，因此每个节点最多包含在一个返回的负环中。

处理负权重的能力使 Bellman-Ford 比 Dijkstra 更具通用性，但在实践中也更慢。

Neo4j GDS 库提供了原始 Bellman-Ford 算法的一种改进版本，称为最短路径更快的算法 (SPFA)。SPFA 通过仅在节点的一个子集上工作而不是在每一步都迭代所有节点集来显著减少 Bellman-Ford 的计算时间。此外，计算是并行化的，以进一步加快计算速度。

语法

本节介绍在每种执行模式下执行 Bellman-Ford 算法所使用的语法。我们将描述命名图语法的变体。要了解有关通用语法变体的更多信息，请参阅语法概述。

每种模式下的 Bellman-Ford 语法

在命名图上以流模式运行 Bellman-Ford。

CALL gds.bellmanFord.stream(
  graphName: String,
  configuration: Map
)
YIELD
  index: Integer,
  sourceNode: Integer,
  targetNode: Integer,
  totalCost: Float,
  nodeIds: List of Integer,
  costs: List of Float,
  route: Path,
  isNegativeCycle: Boolean

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[1]`	是	运行算法所使用的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，将不记录进度百分比。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
1. 在 GDS 会话中，默认值是可用处理器数量

表 3. 结果
名称	类型	描述
index	整数	找到的路径的 0-based 索引。
sourceNode	整数	路径的源节点。
targetNode	整数	路径的目标节点。
totalCost	浮点数	从源到目标的总成本。
nodeIds	整数列表	遍历顺序中的路径上的节点 ID。
costs	浮点数列表	路径上每个节点的累计成本。
route	路径	以 Cypher 实体表示的路径。
isNegativeCycle	布尔值	如果为 true，则发现的路径是负环。否则，它是最短路径。

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

在命名图上以变异模式运行 Bellman-Ford。

CALL gds.bellmanFord.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  containsNegativeCycle: Boolean,
  configuration: Map

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

表 5. 配置
名称	类型	默认值	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图中的新关系的关系类型。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	运行算法所使用的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
mutateNegativeCycles	布尔值	`false`	是	如果设置为 true，任何发现的负环将被添加到内存中的图中。否则，它们将被跳过。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
mutateMillis	整数	向投影图添加关系的毫秒数。
relationshipsWritten	整数	添加的关系数量。
containsNegativeCycle	布尔值	如果发现负环则为 True。
configuration	映射	用于运行算法的配置。

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

在命名图上以写入模式运行 Bellman-Ford。

CALL gds.bellmanFord.write(
  graphName: String,
  configuration: Map
)
YIELD
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  containsNegativeCycle: Boolean,
  configuration: Map

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

表 8. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	运行算法所使用的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，将不记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于在 Neo4j 数据库中持久化计算关系的类型。
writeNegativeCycles	布尔值	`false`	是	如果设置为 true，任何发现的负环将被写回 Neo4j 图。否则，它们将被跳过。
writeNodeIds	布尔值	`false`	是	如果为 true，写入的关系将具有一个 nodeIds 列表属性。
writeCosts	布尔值	`false`	是	如果为 true，写入的关系将具有一个 costs 列表属性。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
2. 在 GDS 会话中，默认值是可用处理器数量

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
writeMillis	整数	将关系写入 Neo4j 的毫秒数。
relationshipsWritten	整数	写入的关系数量。
containsNegativeCycle	布尔值	如果发现负环则为 True。
configuration	映射	用于运行算法的配置。

在命名图上以统计模式运行 Bellman-Ford。

CALL gds.bellmanFord.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  containsNegativeCycle: Boolean,
  configuration: Map

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

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[3]`	是	运行算法所使用的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，将不记录进度百分比。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
3. 在 GDS 会话中，默认值是可用处理器数量

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
containsNegativeCycle	布尔值	如果发现负环则为 True。
configuration	映射	用于运行算法的配置。

示例

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

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

在本节中，我们将演示如何在具体图上运行 Bellman-Ford 算法的示例。目的是说明结果是什么样子，并提供如何在实际设置中使用算法的指南。我们将在一个由少数节点以特定模式连接的小型示例网络图上进行此操作。示例图如下所示

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

CREATE (a:Node {name: 'A'}),
       (b:Node {name: 'B'}),
       (c:Node {name: 'C'}),
       (d:Node {name: 'D'}),
       (e:Node {name: 'E'}),
       (f:Node {name: 'F'}),
       (g:Node {name: 'G'}),
       (h:Node {name: 'H'}),
       (i:Node {name: 'I'}),
       (a)-[:REL {cost: 50}]->(b),
       (a)-[:REL {cost: -50}]->(c),
       (a)-[:REL {cost: 100}]->(d),
       (b)-[:REL {cost: 40}]->(d),
       (c)-[:REL {cost: 40}]->(d),
       (c)-[:REL {cost: 80}]->(e),
       (d)-[:REL {cost: 30}]->(e),
       (d)-[:REL {cost: 80}]->(f),
       (e)-[:REL {cost: 40}]->(f),
       (g)-[:REL {cost: 40}]->(h),
       (h)-[:REL {cost: -60}]->(i),
       (i)-[:REL {cost: 10}]->(g)

此图构建了一个示例网络，其中节点之间的关系具有负权重和正权重。这些权重由 cost 关系属性表示。

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

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

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

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 write 模式。估算算法有助于了解在图上运行算法对内存的影响。当您稍后实际以某种执行模式运行算法时，系统将执行估算。如果估算显示执行超出其内存限制的可能性非常高，则将禁止执行。要了解更多信息，请参阅自动估算和执行阻止。

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

以下将估算在写入模式下运行算法的内存要求

MATCH (source:Node {name: 'A'})
CALL gds.bellmanFord.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
9	12	1424	1424	"1424 字节"

如果图中存在负环，算法支持写入（或变异）负环，这由 writeNegativeCycles (mutateNegativeCycles) 配置参数控制。这需要额外的内存，因为必须跟踪负环。

以下将估算在写入模式下运行算法（包括负环）的内存要求

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

表 14. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
9	12	1648	1648	"1648 字节"

流

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

流式传输无负环

以下将在无负环的组件上以流模式运行 Bellman-Ford

MATCH (source:Node {name: 'A'})
CALL gds.bellmanFord.stream('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, route, isNegativeCycle
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNode,
    gds.util.asNode(targetNode).name AS targetNode,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(route) as route,
    isNegativeCycle as isNegativeCycle
ORDER BY index

表 15. 结果
index	sourceNode	targetNode	totalCost	nodeNames	costs	route	isNegativeCycle
0	"A"	"A"	0.0	["A"]	[0.0]	[Node[0]]	false
1	"A"	"B"	50.0	["A", "B"]	[0.0, 50.0]	[Node[0], Node[1]]	false
2	"A"	"C"	-50.0	["A", "C"]	[0.0, -50.0]	[Node[0], Node[2]]	false
3	"A"	"D"	-10.0	["A", "C", "D"]	[0.0, -50.0, -10.0]	[Node[0], Node[2], Node[3]]	false
4	"A"	"E"	20.0	["A", "C", "D", "E"]	[0.0, -50.0, -10.0, 20.0]	[Node[0], Node[2], Node[3], Node[4]]	false
5	"A"	"F"	60.0	["A", "C", "D", "E", "F"]	[0.0, -50.0, -10.0, 20.0, 60.0]	[Node[0], Node[2], Node[3], Node[4], Node[5]]	false

由于 A 的组件不包含任何负环，因此结果显示了从 A 到其所有可达节点的最短路径。还返回了每个路径的节点 ID 有序列表及其累积成本。Cypher Path 对象通过 path 返回字段返回，它们包含节点对象和具有 cost 属性的虚拟关系。

流式传输有负环

以下将在带负环的组件上以流模式运行 Bellman-Ford

MATCH (source:Node {name: 'G'})
CALL gds.bellmanFord.stream('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, route, isNegativeCycle
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNode,
    gds.util.asNode(targetNode).name AS targetNode,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(route) as route,
    isNegativeCycle as isNegativeCycle
ORDER BY index

表 16. 结果
index	sourceNode	targetNode	totalCost	nodeNames	costs	route	isNegativeCycle
0	"G"	"G"	-10.0	["G", "H", "I", "G"]	[0.0, 40.0, -20.0, -10.0]	[Node[6], Node[7], Node[8], Node[6]]	true

在此示例中，Bellman-Ford 未产生任何最短路径，因为它检测到负环。一个总成本为 -10 的 G 的负环被作为输出发出，isNegativeCycle 字段设置为 true。

统计

在 stats 执行模式下，算法返回一行，其中包含算法结果的摘要。此执行模式没有任何副作用。通过检查 computeMillis 返回项，它可用于评估算法性能。在下面的示例中，我们将省略返回时间。该过程的完整签名可在语法部分找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下将以 stats 模式运行 Bellman Ford

MATCH (source:Node {name: 'A'})
CALL gds.bellmanFord.stats('myGraph', {
  sourceNode: source,
  relationshipWeightProperty: 'cost'
})
YIELD  containsNegativeCycle
RETURN containsNegativeCycle

表 17. 结果
containsNegativeCycle
false

如果我们要发现图是否有任何负环，但又不想计算或存储它们，运行统计模式会很有用。对于此示例，我们可以看到 containsNegativeCycle 字段为 false，因为 A 无法到达任何负环。

变异

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

无负环变异

以下将在无负环的组件上以变异模式运行 Bellman-Ford

MATCH (source:Node {name: 'A'})
CALL gds.bellmanFord.mutate('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    mutateRelationshipType: 'ROUTE'
})
YIELD relationshipsWritten, containsNegativeCycle
RETURN relationshipsWritten, containsNegativeCycle

表 18. 结果
relationshipsWritten	containsNegativeCycle
6	false

执行上述查询后，内存图将使用类型为 ROUTE 的新关系进行更新。由于 containsNegativeCycle 为 false，这些关系表示最短路径。新关系将存储一个名为 totalCost 的属性，对应于从源到目标的最短路径成本。

带负环变异

以下将在带负环的组件上以变异模式运行 Bellman-Ford

MATCH (source:Node {name: 'G'})
CALL gds.bellmanFord.mutate('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    mutateRelationshipType: 'ROUTE',
    mutateNegativeCycles: true
})
YIELD relationshipsWritten, containsNegativeCycle
RETURN relationshipsWritten, containsNegativeCycle

表 19. 结果
relationshipsWritten	containsNegativeCycle
1	true

执行上述查询后，内存图将使用类型为 ROUTE 的单个关系进行更新。由于 containsNegativeCycle 为 true，此关系表示发现的负环。新关系存储一个名为 totalCost 的属性，对应于负环的权重。

请注意，默认情况下，当在变异模式下检测到负环时，它们将不会写回内存图。这可以通过将 mutateNegativeCycles 设置为 true 来绕过，如上述示例所示。

生成的关系始终是有向的，即使输入图是无向的。

写入

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

无负环写入

以下将在无负环的组件上以写入模式运行 Bellman-Ford

MATCH (source:Node {name: 'A'})
CALL gds.bellmanFord.write('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'ROUTE',
    writeNodeIds: true,
    writeCosts: true
})
YIELD relationshipsWritten, containsNegativeCycle
RETURN relationshipsWritten, containsNegativeCycle

表 20. 结果
relationshipsWritten	containsNegativeCycle
6	false

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

带负环写入

以下将在带负环的组件上以写入模式运行 Bellman-Ford

MATCH (source:Node {name: 'G'})
CALL gds.bellmanFord.write('myGraph', {
    sourceNode: source,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'ROUTE',
    writeNodeIds: true,
    writeCosts: true,
    writeNegativeCycles:true
})
YIELD relationshipsWritten, containsNegativeCycle
RETURN relationshipsWritten, containsNegativeCycle

表 21. 结果
relationshipsWritten	containsNegativeCycle
1	true

执行上述查询后，一个类型为 ROUTE 的关系被写回 Neo4j 图。由于 containsNegativeCycle 为 true，该关系表示一个负环。

与 mutate 模式类似，当遇到负环时，默认行为是不将它们写回 Neo4j 数据库。我们可以像示例中那样将 writeNegativeCycles 设置为 true 来覆盖此设置。

写入的关系始终是有向的，即使输入图是无向的。