所有节点对的最短路径

所有节点对的最短路径 (APSP) 计算所有节点对之间的最短（加权）路径。该算法经过优化，使其比对图中每对节点调用单源最短路径算法更快。

此功能处于 Alpha 级别。有关功能级别的更多信息，请参阅 API 级别.

有向

词汇表

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

历史和解释

某些节点对可能无法相互到达，因此这两对节点之间不存在最短路径。在这种情况下，算法将返回这两对节点之间的 Infinity 值作为结果。

GDS 包含函数，例如 gds.util.isFinite，可帮助从结果中过滤掉无限值。从 Neo4j 5 开始，Infinity 字面量现在也包含在 Cypher 中。

用例 - 何时使用所有节点对的最短路径算法

所有节点对的最短路径算法用于城市服务系统问题，例如城市设施的位置或货物分发或配送。一个例子是确定交通网格不同部分的预期交通负荷。有关更多信息，请参阅城市运筹学.
所有节点对的最短路径用作 REWIRE 数据中心设计算法的一部分，该算法可以找到具有最大带宽和最小延迟的网络。有关此方法的更多详细信息，请参阅 "REWIRE：数据中心网络设计的一种基于优化的框架"

语法

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

CALL gds.allShortestPaths.stream(
  graphName: string,
  configuration: map
)
YIELD sourceNodeId, targetNodeId, distance

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含在内。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含在内。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。

表 3. 结果
名称	类型	描述
sourceNodeId	整数	源节点。
targetNodeId	整数	目标节点。
distance	浮点数	从源到目标的最短路径的距离。

所有对最短路径算法示例

以下将创建一个示例图

CREATE (a:Loc {name: 'A'}),
       (b:Loc {name: 'B'}),
       (c:Loc {name: 'C'}),
       (d:Loc {name: 'D'}),
       (e:Loc {name: 'E'}),
       (f:Loc {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);

以下将使用 Cypher 投影投影并存储一个无向图

MATCH (src:Loc)-[r:ROAD]->(trg:Loc)
RETURN gds.graph.project(
  'cypherGraph',
  src,
  trg,
  {
    relationshipType: type(r),
    relationshipProperties: r { .cost }
  },
  { undirectedRelationshipTypes: ['ROAD'] }
)

以下将运行算法，将图视为无向图

CALL gds.allShortestPaths.stream('cypherGraph', {
  relationshipWeightProperty: 'cost'
})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance
WHERE gds.util.isFinite(distance) = true
WITH gds.util.asNode(sourceNodeId) AS source, gds.util.asNode(targetNodeId) AS target, distance WHERE source <> target

RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC
LIMIT 10

表 4. 结果
source	target	distance
"A"	"F"	160.0
"F"	"A"	160.0
"A"	"E"	120.0
"E"	"A"	120.0
"B"	"F"	110.0
"C"	"F"	110.0
"F"	"B"	110.0
"F"	"C"	110.0
"A"	"D"	90.0
"D"	"A"	90.0