全对最短路径 (All Pairs Shortest Path)

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

术语表

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

历史与解释

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

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

使用场景 - 何时使用全对最短路径算法

全对最短路径算法常用于城市服务系统问题，例如城市设施选址或货物配送。一个典型的例子是确定交通网络中不同路段的预期交通负荷。更多信息请参阅《城市运筹学》(Urban Operations Research)。
全对最短路径算法被用作 REWIRE 数据中心设计算法的一部分，该算法用于寻找具有最大带宽和最小延迟的网络。关于此方法的更多详细信息，请参阅《REWIRE：一种基于优化的数据中心网络设计框架》(REWIRE: An Optimization-based Framework for Data Center Network Design)

语法

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

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

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

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

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

全对最短路径算法示例

以下代码将创建一个示例图

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)

在 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. 结果
source	target（目标）	距离
"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