所有对最短路径

此功能在 Aura 无服务器图分析中不可用。

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

有向

词汇表

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

历史与解释

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

GDS 包含诸如函数 gds.util.isFinite 之类的函数，以帮助从结果中过滤无穷大值。从 Neo4j 5 开始，Infinity 字面量也已包含在 Cypher 中。

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

所有对最短路径算法用于解决城市服务系统问题，例如城市设施的选址或商品的配送和交付。一个例子是确定交通网络不同路段的预期交通负荷。欲了解更多信息，请参阅 Urban Operations Research。
所有对最短路径被用作 REWIRE 数据中心设计算法的一部分，该算法旨在找到具有最大带宽和最小延迟的网络。有关此方法的更多详细信息，请参见《REWIRE：基于优化的数据中心网络设计框架》

语法

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

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

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

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

表 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'] }
)

内存估算

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

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

以下将估算运行算法所需的内存

CALL gds.allShortestPaths.stream.estimate('cypherGraph', {
  relationshipWeightProperty: 'cost'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 4. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	18	1264	1264	"1264 字节"

流模式

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

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

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

表 5. 结果
源	目标	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