Delta-Stepping 单源最短路径

简介

Delta-Stepping 最短路径算法用于计算图中源节点到所有可达节点之间的所有最短路径。该算法支持具有正向关系权重的加权图。若要计算源节点到单个目标节点之间的最短路径，可以使用 Dijkstra 源-目标算法。

与 Dijkstra 单源算法相比，Delta-Stepping 算法是一种距离修正算法。这一特性使其能够并行遍历图。该算法保证始终能找到源节点与目标节点之间的最短路径。然而，如果两个节点之间存在多条最短路径，则不保证每次计算都返回同一条路径。

Neo4j 图分析的实现基于 [1]，并融合了 [2] 中讨论的桶融合（bucket fusion）优化。算法实现使用多线程执行。

有关此算法的更多信息，请参阅

语法

本节介绍执行 Delta-Stepping 算法所使用的语法。

运行 Delta-Stepping。

CALL Neo4j_Graph_Analytics.graph.delta_stepping(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);

1	计算池选择器。
2	表引用的可选前缀。
3	项目配置。
4	计算配置。
5	写入配置。

表 1. 参数
名称	类型	默认	可选	描述
computePoolSelector	字符串	`不适用`	否	用于运行 Delta-Stepping 单源作业的计算池选择器。
配置	Map	`{}`	否	用于图项目、算法计算和结果回写的配置。

配置映射由以下三个条目组成。

有关以下项目配置的更多详细信息，请参阅项目文档。

表 2. 项目配置
名称	类型
nodeTables	节点表列表。
relationshipTables	关系类型到关系表的映射。

表 3. 计算配置
名称	类型	默认	可选	描述
resultProperty	字符串	`'total_cost'`	是	将回写到 Snowflake 数据库的关系属性。
resultRelationshipType	字符串	`'PATH'`	是	用于回写到 Snowflake 数据库的关系类型。
sourceNode	整数或字符串	`不适用`	否	源节点标识符。
sourceNodeTable	字符串	`不适用`	否	用于映射源节点标识符的表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
delta	浮点数	`2.0`	是	用于对到源节点具有相同暂定距离的节点进行分组的桶宽度（bucket width）。

有关以下写入配置的更多详细信息，请参阅写入文档。

表 4. 写入配置
名称	类型	默认	可选	描述
sourceLabel	字符串	`不适用`	否	内存图中待回写关系起始节点的节点标签。
targetLabel	字符串	`不适用`	否	内存图中待回写关系结束节点的节点标签。
outputTable	字符串	`不适用`	否	关系写入的 Snowflake 数据库表。
关系类型 (relationshipType)	字符串	`'PATH'`	是	将回写到 Snowflake 数据库的关系类型。
relationshipProperty	字符串	`'total_cost'`	是	将回写到 Snowflake 数据库的关系属性。

Delta

delta 参数定义了一个范围，用于将到起始节点具有相同暂定距离的节点进行分组。这些范围也称为桶。在算法的每次迭代中，暂定距离最小的非空桶将并行处理。delta 参数是该算法的主要调整旋钮，用于控制可并行处理的工作负载。通常，对于幂律图（其中许多节点可以在几跳内到达），建议使用较小的 delta 值（例如 2）。对于高直径图（如交通网络），建议使用较大的 delta 值（例如 10000）。请注意，该值可能会根据图的拓扑结构和关系属性的值范围而有所不同。

示例

现在我们来看看如何将 Delta-Stepping 应用于道路网络。

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.locations (NODEID VARCHAR);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.locations VALUES
  ('A'),
  ('B'),
  ('C'),
  ('D'),
  ('E'),
  ('F');

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.roads (SOURCENODEID VARCHAR, TARGETNODEID VARCHAR, COST FLOAT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.roads VALUES
  ('A', 'B',  50),
  ('A', 'C',  50),
  ('A', 'D', 100),
  ('B', 'D',  40),
  ('C', 'D',  40),
  ('C', 'E',  80),
  ('D', 'E',  30),
  ('D', 'F',  80),
  ('E', 'F',  40);

此图构建了一个位置之间有道路的交通网络。像现实世界一样，图中的道路具有不同的长度。这些长度由 cost 关系属性表示。

在下面的示例中，我们将演示如何使用该图应用 Delta-Stepping 最短路径算法。

运行作业

运行 Delta-Stepping 作业包含三个步骤：投影（Project）、计算（Compute）和写入（Write）。

以下代码将运行该算法，并将结果写回您的表中

CALL Neo4j_Graph_Analytics.graph.delta_stepping('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'LOCATIONS' ],
        'relationshipTables': {
            'roads': {
                'sourceTable': 'LOCATIONS',
                'targetTable': 'LOCATIONS'
            }
        }
    },
    'compute': {
        'sourceNode': 'A',
        'sourceNodeTable': 'LOCATIONS',
        'relationshipWeightProperty': 'COST'
    },
    'write': [{
        'sourceLabel': 'LOCATIONS',
        'targetLabel': 'LOCATIONS',
        'outputTable': 'PATHS'
    }]
});

表 5. 结果
JOB_ID	JOB_STATUS	JOB_START	JOB_END	JOB_RESULT
job_a58bc1934def4d5ca9022528ea2e55a1	SUCCESS	2025-07-17 13:22:37.239	2025-07-17 13:22:41.800	{ "delta_stepping_1": { "computeMillis": 19, "configuration": { "concurrency": 6, "delta": 2, "resultRelationshipType": "PATH", "nodeLabels": [ "" ], "relationshipTypes": [ "" ], "relationshipWeightProperty": "COST", "sourceNode": "A", "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS" } }, "project_1": { "graphName": "snowgraph", "nodeCount": 6, "nodeLabels": ..., "nodeMillis": 111, "relationshipCount": 9, "relationshipMillis": 263, "relationshipTypes": ..., "totalMillis": 374 }, "write_relationship_type_1": { "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS", "relationshipProperty": "[SOURCENODEID, TARGETNODEID, NODEIDS, NODELABELS, COSTS, TOTALCOST]", "relationshipType": "PATH", "rowsWritten": 6, "writeMillis": 1798 } }

表 5. 结果

JOB_ID

JOB_STATUS

JOB_START

JOB_END

JOB_RESULT

job_a58bc1934def4d5ca9022528ea2e55a1

SUCCESS

2025-07-17 13:22:37.239

2025-07-17 13:22:41.800

{
  "delta_stepping_1": {
    "computeMillis": 19,
    "configuration": {
      "concurrency": 6,
      "delta": 2,
      "resultRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": "A",
      "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS"
    }
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeLabels": ...,
    "nodeMillis": 111,
    "relationshipCount": 9,
    "relationshipMillis": 263,
    "relationshipTypes": ...,
    "totalMillis": 374
  },
  "write_relationship_type_1": {
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS",
    "relationshipProperty": "[SOURCENODEID, TARGETNODEID, NODEIDS, NODELABELS, COSTS, TOTALCOST]",
    "relationshipType": "PATH",
    "rowsWritten": 6,
    "writeMillis": 1798
  }
}

返回的结果包含有关任务执行的信息。此外，最短路径已写回 Snowflake 数据库。我们可以像这样进行查询

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PATHS;

这显示了存储在数据库中的计算结果

表 6. 结果
SOURCENODEID	TARGETNODEID	NODEIDS	NODELABELS	COSTS	TOTALCOST
A	A	["A"]	["LOCATIONS"]	[0]	0
A	B	["A", "B"]	["LOCATIONS", "LOCATIONS"]	[0, 50]	50
A	C	["A", "C"]	["LOCATIONS", "LOCATIONS"]	[0, 50]	50
A	D	["A", "B", "D"]	["LOCATIONS", "LOCATIONS", "LOCATIONS"]	[0, 50, 90]	90
A	E	["A", "B", "D", "E"]	["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]	[0, 50, 90, 120]	120
A	F	["A", "B", "D", "E", "F"]	["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]	[0, 50, 90, 120, 160]	160

结果显示了节点 A 与图中所有其他可达节点之间最短路径的总成本。它还显示了为找到最短路径所遍历的节点 ID（及其标签）的有序列表，以及已访问节点的累积成本。这可以在示例图中进行验证。

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