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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	针对算法特定内容和/或图过滤的配置。

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

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

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

在命名图上以 mutate 模式运行 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	针对算法特定内容和/或图过滤的配置。

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

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

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

在命名图上以 write 模式运行 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	针对算法特定内容和/或图过滤的配置。

表 8. 配置
名称	类型	默认值	可选	描述
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
writeNegativeCycles	布尔值	`假`	是	如果设置为真，则将任何发现的负循环写回 Neo4j 图。否则将跳过它们。

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

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

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

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

表 11. 配置
名称	类型	默认值	可选	描述
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
containsNegativeCycle	布尔值	如果发现负循环，则为真。
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 的更多详细信息，请参阅内存估计。

以下操作将估计以 write 模式运行算法的内存需求

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	1336	1336	"1336 字节"

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

以下操作将估计以 write 模式运行算法的内存需求，包括负循环

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	1448	1448	"1448 字节"

流

在 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]]	假
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"	-10.0	["A", "C", "D"]	[0.0, -50.0, -10.0]	[Node[0], Node[2], Node[3]]	假
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]]	假
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]]	假

由于 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]]	真

对于此示例，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
假

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

变异

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

无负循环的 Mutate

以下将在 Mutate 模式下对无负循环的组件运行 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	假

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

带负循环的 Mutate

以下将在 Mutate 模式下对带负循环的组件运行 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	真

执行上述查询后，内存中的图将使用一个类型为 ROUTE 的关系进行更新。由于 containsNegativeCycle 为 true，该关系代表检测到的负循环。新的关系存储一个名为 totalCost 的属性，对应于负循环的权重。

请注意，默认情况下，在 Mutate 模式下检测到负循环时，它们不会被写回内存中的图。可以通过将 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	假

上述查询将 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	真

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

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

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