Bellman-Ford 单源最短路径

术语表

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

简介

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

与仅适用于非负关系权重的 Dijkstra 算法相比，Bellman-Ford 算法还能够处理包含负权重的图，前提是源节点无法到达任何参与负环的节点。图中的“环”是指起点和终点相同的路径。“负环”是指关系权重之和为负数的环。当存在负环时，无法简单地定义最短路径，因为我们可以通过多次遍历负环来不断获得越来越小的成本。

当 Bellman-Ford 算法检测到负环时，它将尝试返回负环而不是最短路径。请注意，由于算法为了支持并行执行而进行了修改，在某些情况下可能无法枚举出所有的负环。

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

能够处理负权重使得 Bellman-Ford 比 Dijkstra 更具通用性，但在实际应用中速度较慢。

Neo4j GDS 库提供了一种名为最短路径快速算法 (SPFA) 的 Bellman-Ford 算法适配版本。SPFA 通过仅处理节点的一个子集，而不是在每一步迭代所有节点，显著降低了 Bellman-Ford 的计算时间。此外，计算过程经过并行化处理，进一步提高了计算速度。

语法

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

每种模式下的 Bellman-Ford 语法

在命名图上以流 (stream) 模式运行 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	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

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

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

变异（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	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

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

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

写入（write）模式在 Neo4j 数据库中创建新的关系。每种关系代表从源节点到目标节点的一条路径。额外的路径信息使用关系属性存储。默认情况下，写入模式存储 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	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认	可选	描述
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
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 列表属性。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
2. 在 GDS 会话中，默认值为可用处理器的数量。

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

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

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

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

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

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

示例

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

这些示例将 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 Bytes"

如果图中存在负环，算法支持写入（或变异）这些负环，这由 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 Bytes"

流模式 (Stream)

在 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 返回字段提供，它们包含节点对象和具有 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 没有产生任何最短路径。输出显示了 G 的一个总成本为 -10 的负环，且 isNegativeCycle 字段设置为 true。

统计模式 (Stats)

在 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)

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)

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 来覆盖此设置。

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