Yen 最短路径算法

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特征。该算法在有向图上定义明确。
有向: 有向特征。该算法会忽略图的方向。
有向: 有向特征。该算法不会在有向图上运行。
无向: 无向特征。该算法在无向图上定义明确。
无向: 无向特征。该算法会忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法会以相同的方式处理所有选定节点，而不管它们的标签。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法会以相同的方式处理所有选定关系，而不管它们的类型。
加权关系: 加权特征。该算法支持使用关系属性作为权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法会将每个关系视为同样重要，忽略任何关系权重的值。

简介

Yen 最短路径算法计算两个节点之间的多个最短路径。该算法通常称为 Yen 的 k-最短路径算法，其中 k 是要计算的最短路径数。该算法支持具有正关系权重的加权图。它还尊重相同两个节点之间的并行关系，以便计算多个最短路径。

对于 k = 1，该算法的行为与 Dijkstra 最短路径算法完全相同，并返回最短路径。对于 k = 2，该算法将返回相同源节点和目标节点之间的最短路径和第二短路径。一般来说，对于 k = n，该算法最多会计算 n 条路径，这些路径是按其总成本的顺序发现的。

GDS 实现基于原始描述。对于实际路径计算，Yen 算法使用 Dijkstra 最短路径算法。该算法确保不会再次遍历已经发现的最短路径。

算法实现是并行的，但受限于源目标路径中的节点数量。如果预计这些路径的长度很小（即，只有几个新节点），则不建议设置高并发值，因为一些核心可能处于闲置状态。

语法

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

Yen 的语法按模式

在命名的图上以流模式运行 Yen。

CALL gds.shortestPath.yens.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	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`n/a`	否	Neo4j 目标节点或节点 ID。
k	整数	`1`	是	在源节点和目标节点之间计算的最短路径数。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

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

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

在命名的图上以 mutate 模式运行 Yen。

CALL gds.shortestPath.yens.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。
targetNode	整数	`n/a`	否	Neo4j 目标节点或节点 ID。
k	整数	`1`	是	在源节点和目标节点之间计算的最短路径数。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

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

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

在命名的图上以 write 模式运行 Yen。

CALL gds.shortestPath.yens.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	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`n/a`	否	用于将计算出的关系持久化到 Neo4j 数据库中的关系类型。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`n/a`	否	Neo4j 目标节点或节点 ID。
k	整数	`1`	是	在源节点和目标节点之间计算的最短路径数。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
writeNodeIds	布尔值	`false`	是	如果为 true，则写入的关系具有 nodeIds 列表属性。
writeCosts	布尔值	`false`	是	如果为 true，则写入的关系具有 costs 列表属性。

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

示例

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

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

在本节中，我们将展示在具体图上运行 Yen 算法的示例。目的是说明结果的外观，并提供如何在实际环境中使用该算法的指南。我们将在一个小型交通网络图上执行此操作，该图由少数几个以特定模式连接的节点组成。示例图如下所示

以下 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 } }
)

在以下示例中，我们将演示使用该图使用 Yen 最短路径算法的方法。

内存估算

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

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

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

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.write.estimate('myGraph', {
    sourceNode: source,
    targetNode: target,
    k: 3,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'PATH'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 10. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	9	4648	4648	"4648 字节"

流

在 stream 执行模式中，算法为每个源目标对返回最短路径。这使我们能够直接检查结果，或者在没有副作用的情况下在 Cypher 中对其进行后处理。

有关 stream 模式的更多详细信息，请参阅流。

以下操作将运行算法并流式传输结果

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.stream('myGraph', {
    sourceNode: source,
    targetNode: target,
    k: 3,
    relationshipWeightProperty: 'cost'
})
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

表 11. 结果
index	sourceNodeName	targetNodeName	totalCost	nodeNames	costs	path
0	"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]]
1	"A"	"F"	160.0	["A", "C", "D", "E", "F"]	[0.0, 50.0, 90.0, 120.0, 160.0]	[Node[0], Node[2], Node[3], Node[4], Node[5]]
2	"A"	"F"	170.0	["A", "B", "D", "F"]	[0.0, 50.0, 90.0, 170.0]	[Node[0], Node[1], Node[3], Node[5]]

结果显示了节点 A 和节点 F 之间的三个最短路径。前两个路径的总成本相同，但第一个路径从 A 到 D 经过 B 节点，而第二个路径经过 C 节点。第三条路径的总成本更高，因为它直接从 D 到 F 使用成本为 80 的关系，而前两条路径通过 E 的迂回路线的成本为 70。这可以在示例图中得到验证。Cypher 路径对象可以通过 path 返回字段返回。路径对象包含节点对象和具有 cost 属性的虚拟关系。

变异

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

mutate 模式在多个算法结合使用时特别有用。

有关 mutate 模式的更多详细信息，请参阅变异。

以下操作将在 mutate 模式下运行算法

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.mutate('myGraph', {
    sourceNode: source,
    targetNode: target,
    k: 3,
    relationshipWeightProperty: 'cost',
    mutateRelationshipType: 'PATH'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 12. 结果
relationshipsWritten
3

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

生成的關係始终是定向的，即使輸入圖是無向的。

写入

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

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

以下操作将在 write 模式下运行算法

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.write('myGraph', {
    sourceNode: source,
    targetNode: target,
    k: 3,
    relationshipWeightProperty: 'cost',
    writeRelationshipType: 'PATH',
    writeNodeIds: true,
    writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 13. 结果
relationshipsWritten
3

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

写入的关系始终是定向的，即使輸入圖是無向的。