Dijkstra 源-目标最短路径

有向

无向

异构节点

异构关系

带权重关系

词汇表

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

简介

Dijkstra 最短路径算法计算节点之间的最短路径。该算法支持具有正关系权重的加权图。Dijkstra 源-目标算法计算源节点与目标节点列表之间的最短路径。要计算从源节点到所有可达节点的所有路径，可以使用Dijkstra 单源最短路径。

GDS 实现基于原始描述，并使用二叉堆作为优先级队列。该实现也用于 A* 和 Yen 算法。该算法实现使用单线程执行。更改并发配置无效。

语法

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

每种模式下的 Dijkstra 语法

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

CALL gds.shortestPath.dijkstra.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	String	`不适用`	否	目录中存储的图的名称。
configuration	Map	`{}`	是	算法特定配置和/或图筛选。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	String 列表	`['*']`	是	使用给定节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	String 列表	`['*']`	是	使用给定关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	Integer	`1`	是	该算法是单线程的，更改并发参数对运行时没有影响。
jobId	String	`内部生成`	是	可提供用于更轻松地跟踪算法进度的 ID。
logProgress	Boolean	`true`	是	如果禁用，将不会记录进度百分比。
sourceNode	Integer	`不适用`	否	Neo4j 源节点或节点 ID。
targetNodes	Integer 或 Integer 列表	`不适用`	否	Neo4j 目标节点或节点 ID。
targetNode	Integer	`不适用`	否	Neo4j 目标节点或节点 ID。已弃用，请改用 `targetNodes`。
relationshipWeightProperty	String	`null`	是	用作权重的关系属性的名称。如果未指定，算法将以无权重模式运行。

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

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

在命名图上以变更模式运行 Dijkstra。

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

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

表 5. 配置
名称	类型	默认值	可选	描述
mutateRelationshipType	String	`不适用`	否	用于写入投影图的新关系的关系类型。
nodeLabels	String 列表	`['*']`	是	使用给定节点标签筛选命名图。
relationshipTypes	String 列表	`['*']`	是	使用给定关系类型筛选命名图。
concurrency	Integer	`4`	是	用于运行算法的并发线程数。
jobId	String	`内部生成`	是	可提供用于更轻松地跟踪算法进度的 ID。
sourceNode	Integer	`不适用`	否	Neo4j 源节点或节点 ID。
targetNodes	Integer 或 Integer 列表	`不适用`	否	Neo4j 目标节点或节点 ID。
targetNode	Integer	`不适用`	否	Neo4j 目标节点或节点 ID。已弃用，请改用 `targetNodes`。
relationshipWeightProperty	String	`null`	是	用作权重的关系属性的名称。如果未指定，算法将以无权重模式运行。

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

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

在命名图上以写入模式运行 Dijkstra。

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

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

表 8. 配置
名称	类型	默认值	可选	描述
nodeLabels	String 列表	`['*']`	是	使用给定节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	String 列表	`['*']`	是	使用给定关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	Integer	`1`	是	该算法是单线程的，更改并发参数对运行时没有影响。
jobId	String	`内部生成`	是	可提供用于更轻松地跟踪算法进度的 ID。
logProgress	Boolean	`true`	是	如果禁用，将不会记录进度百分比。
writeConcurrency	Integer	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	String	`不适用`	否	用于将计算出的关系持久化到 Neo4j 数据库中的关系类型。
sourceNode	Integer	`不适用`	否	Neo4j 源节点或节点 ID。
targetNodes	Integer 或 Integer 列表	`不适用`	否	Neo4j 目标节点或节点 ID。
targetNode	Integer	`不适用`	否	Neo4j 目标节点或节点 ID。已弃用，请改用 `targetNodes`。
relationshipWeightProperty	String	`null`	是	用作权重的关系属性的名称。如果未指定，算法将以无权重模式运行。
writeNodeIds	Boolean	`false`	是	如果为 true，则写入的关系具有 nodeIds 列表属性。
writeCosts	Boolean	`false`	是	如果为 true，则写入的关系具有 costs 列表属性。

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

示例

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

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

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

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

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

内存估算

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

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

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

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

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

流

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

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

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

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.dijkstra.stream('myGraph', {
    sourceNode: source,
    targetNodes: target,
    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. 结果
索引	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]]

结果显示了节点 A 和节点 F 之间最短路径的总成本。它还显示了遍历以查找最短路径的节点 ID 的有序列表，以及已访问节点的累计成本。这可以在示例图中验证。Cypher Path 对象可以通过 path 返回字段返回。Path 对象包含节点对象和具有 cost 属性的虚拟关系。

变更

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

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

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

以下将以 mutate 模式运行算法：

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

表 12. 结果
relationshipsWritten
1

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

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

写入

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

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

以下将以 write 模式运行算法：

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

表 13. 结果
relationshipsWritten
1

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

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

指定多个目标

可以计算源节点和多个目标节点之间的最短路径。这可以通过为 targetNodes 提供节点或节点 ID 列表来实现，如下例所示。

以下将以 stream 模式运行算法：

MATCH (source:Location {name: 'A'}), (targetD:Location {name: 'D'}),  (targetF:Location {name: 'F'})
CALL gds.shortestPath.dijkstra.stream('myGraph', {
    sourceNode: source,
    targetNodes: [targetD,targetF],
    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

表 14. 结果
索引	sourceNodeName	targetNodeName	totalCost	nodeNames	costs	path
0	"A"	"D"	90.0	["A", "B", "D"]	[0.0, 50.0, 90.0]	[Node[0], Node[1], Node[3]]
1	"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]]

请注意，这无法通过 targetNode 配置参数实现。