A* 最短路径

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

A*（发音为“A-Star”）最短路径算法计算两个节点之间的最短路径。A* 是一种启发式搜索算法，因为它使用启发式函数来指导图遍历。该算法支持具有正关系权重的加权图。

与 Dijkstra 最短路径算法不同，下一个要搜索的节点不是仅根据已计算的距离来选择的。相反，该算法将已计算的距离与启发式函数的结果相结合。该函数以节点作为输入，并返回一个对应于从该节点到达目标节点的成本的值。在每次迭代中，图遍历从具有最低组合成本的节点继续。

在 GDS 中，A* 算法基于 Dijkstra 最短路径算法。启发式函数为海弗森距离，该函数定义了球体上两点之间的距离。此处，球体为地球，点为存储在图中节点上的地理坐标。

算法实现使用单个线程执行。更改并发配置无效。

需求

在 GDS 中，用于指导搜索的启发式函数为海弗森公式。该公式根据两点的经度和纬度计算球体上两点之间的距离。距离以海里计算。

为了保证找到最优解，即两点之间的最短路径，启发式函数必须是可采纳的。要成为可采纳的，函数不得高估到目标的距离，即路径的最低可能成本必须始终大于或等于启发式函数。

这导致了对输入图的关系权重的要求。关系权重必须表示两个节点之间的距离，并且理想情况下按海里缩放。公里或英里也可以使用，但启发式函数最适合海里。

语法

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

每种模式下的 A* 语法

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

CALL gds.shortestPath.astar.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	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`n/a`	否	Neo4j 目标节点或节点 ID。
latitudeProperty	浮点数	`n/a`	否	存储纬度值的节点属性。
longitudeProperty	浮点数	`n/a`	否	存储经度值的节点属性。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将不加权运行。

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

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

在命名图上以 mutate 模式运行 A*。

CALL gds.shortestPath.astar.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。
latitudeProperty	浮点数	`n/a`	否	存储纬度值的节点属性。
longitudeProperty	浮点数	`n/a`	否	存储经度值的节点属性。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将不加权运行。

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

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

在命名图上以 write 模式运行 A*。

CALL gds.shortestPath.astar.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	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`n/a`	否	用于将计算出的关系持久化到 Neo4j 数据库中的关系类型。
sourceNode	整数	`n/a`	否	Neo4j 源节点或节点 ID。
targetNode	整数	`n/a`	否	Neo4j 目标节点或节点 ID。
latitudeProperty	浮点数	`n/a`	否	存储纬度值的节点属性。
longitudeProperty	浮点数	`n/a`	否	存储经度值的节点属性。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将不加权运行。
writeNodeIds	布尔值	`假`	是	如果为真，则写入的关系具有 nodeIds 列表属性。
writeCosts	布尔值	`假`	是	如果为真，则写入的关系具有 costs 列表属性。

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

示例

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

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

在本节中，我们将展示在具体图上运行 A* 算法的示例。目的是说明结果是什么样子，并提供有关如何在实际环境中使用该算法的指南。我们将在少数节点以特定模式连接的小型交通网络图上进行此操作。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE (a:Station {name: 'Kings Cross',         latitude: 51.5308, longitude: -0.1238}),
       (b:Station {name: 'Euston',              latitude: 51.5282, longitude: -0.1337}),
       (c:Station {name: 'Camden Town',         latitude: 51.5392, longitude: -0.1426}),
       (d:Station {name: 'Mornington Crescent', latitude: 51.5342, longitude: -0.1387}),
       (e:Station {name: 'Kentish Town',        latitude: 51.5507, longitude: -0.1402}),
       (a)-[:CONNECTION {distance: 0.7}]->(b),
       (b)-[:CONNECTION {distance: 1.3}]->(c),
       (b)-[:CONNECTION {distance: 0.7}]->(d),
       (d)-[:CONNECTION {distance: 0.6}]->(c),
       (c)-[:CONNECTION {distance: 1.3}]->(e)

该图表示车站的交通网络。每个车站都有一个地理坐标，由 latitude 和 longitude 属性表示。车站通过连接连接。我们使用 distance 属性作为关系权重，表示车站之间的距离（公里）。算法将根据已行驶的距离和到目标车站的距离选择搜索中的下一个节点。

以下语句将使用 Cypher 投影投影图，并将其存储在图目录中，名称为“myGraph”。

MATCH (source:Station)-[r:CONNECTION]->(target:Station)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {
    sourceNodeProperties: source { .latitude, .longitude },
    targetNodeProperties: target { .latitude, .longitude },
    relationshipProperties: r { .distance }
  }
)

在以下示例中，我们将演示使用此图的 A* 最短路径算法的使用。

内存估算

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

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

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

MATCH (source:Station {name: 'Kings Cross'}), (target:Station {name: 'Kentish Town'})
CALL gds.shortestPath.astar.write.estimate('myGraph', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    writeRelationshipType: 'PATH'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 10. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
5	5	1016	1016	"1016 字节"

流

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

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

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

MATCH (source:Station {name: 'Kings Cross'}), (target:Station {name: 'Kentish Town'})
CALL gds.shortestPath.astar.stream('myGraph', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    relationshipWeightProperty: 'distance'
})
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	"国王十字"	"肯特郡镇"	3.3	["国王十字", "尤斯顿", "卡姆登镇", "肯特郡镇"]	[0.0, 0.7, 2.0, 3.3]	[节点[0]，节点[1]，节点[2]，节点[4]]

结果显示了图中节点 国王十字 和 肯特郡镇 之间最短路径的总成本。它还显示了为找到最短路径而遍历的节点 ID 的有序列表以及访问节点的累积成本。这可以在示例图中进行验证。Cypher 路径对象可以通过 path 返回字段返回。路径对象包含节点对象和具有 cost 属性的虚拟关系。

变异

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

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

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

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

MATCH (source:Station {name: 'Kings Cross'}), (target:Station {name: 'Kentish Town'})
CALL gds.shortestPath.astar.mutate('myGraph', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    relationshipWeightProperty: 'distance',
    mutateRelationshipType: 'PATH'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 12. 结果
relationshipsWritten
1

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

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

写入

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

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

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

MATCH (source:Station {name: 'Kings Cross'}), (target:Station {name: 'Kentish Town'})
CALL gds.shortestPath.astar.write('myGraph', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    relationshipWeightProperty: 'distance',
    writeRelationshipType: 'PATH',
    writeNodeIds: true,
    writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 13. 结果
relationshipsWritten
1

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

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