彦氏最短路径算法

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

彦氏最短路径算法计算两个节点之间的多条最短路径。该算法通常被称为彦氏 k-最短路径算法，其中 k 是要计算的最短路径的数量。该算法支持具有正关系权重的加权图。在计算多条最短路径时，它也考虑同一两个节点之间的并行关系。

当k = 1时，该算法的行为与Dijkstra 最短路径算法完全相同，并返回最短路径。当k = 2时，该算法返回同一源节点和目标节点之间的最短路径和次短路径。通常，当k = n时，该算法最多计算n条路径，这些路径按其总成本的顺序发现。

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

该算法实现是并行化的，但受限于源-目标路径中的节点数量。如果这些路径预计长度较短（即只有少量新节点），则不建议将并发值设置得过高，因为部分核心可能未被充分利用。

语法

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

彦氏算法各模式的语法

在命名图上以流模式运行彦氏算法。

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

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

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

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

在命名图上以变异模式运行彦氏算法。

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

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

表 5. 配置
名称	类型	默认值	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`不适用`	否	Neo4j 目标节点或节点 ID。
k	整数	`1`	是	要计算的源节点和目标节点之间的最短路径数量。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性名称。如果未指定，算法将运行非加权模式。

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

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

在命名图上以写入模式运行彦氏算法。

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

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

表 8. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`真`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于在 Neo4j 数据库中持久化计算出的关系的关系类型。
sourceNode	整数	`不适用`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`不适用`	否	Neo4j 目标节点或节点 ID。
k	整数	`1`	是	要计算的源节点和目标节点之间的最短路径数量。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性名称。如果未指定，算法将运行非加权模式。
writeNodeIds	布尔值	`假`	是	如果为 true，则写入的关系具有`nodeIds`列表属性。
writeCosts	布尔值	`假`	是	如果为 true，则写入的关系具有`costs`列表属性。
2. 在GDS 会话中，默认值为可用处理器数量

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

示例

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

示例通常使用Cypher 投影。原生投影将在未来的版本中弃用。

在本节中，我们将展示在具体图上运行彦氏算法的示例。目的是说明结果如何，并提供在实际环境中如何使用该算法的指南。我们将在一个由少量节点以特定模式连接的小型传输网络图上进行此操作。示例图如下所示：

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

在以下示例中，我们将演示如何使用此图运行彦氏最短路径算法。

内存估算

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

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

以下将估算以写入模式运行算法所需的内存：

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

流式

在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]	[节点[0], 节点[1], 节点[3], 节点[4], 节点[5]]
1	"A"	"F"	160.0	["A", "C", "D", "E", "F"]	[0.0, 50.0, 90.0, 120.0, 160.0]	[节点[0], 节点[2], 节点[3], 节点[4], 节点[5]]
2	"A"	"F"	170.0	["A", "B", "D", "F"]	[0.0, 50.0, 90.0, 170.0]	[节点[0], 节点[1], 节点[3], 节点[5]]

结果显示了节点A和节点F之间的三条最短路径。前两条路径的总成本相同，但第一条路径通过B节点从A遍历到D，而第二条路径通过C节点遍历。第三条路径的总成本更高，因为它直接使用成本为80的关系从D到F，而前两条路径通过E的绕道成本为70。这可以在示例图中验证。Cypher Path 对象可以通过path返回字段返回。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。

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