Dijkstra 源-目标最短路径

简介

Dijkstra 最短路径算法计算节点之间的最短路径。该算法支持带有正关系权重的加权图。Dijkstra 源-目标算法计算源节点与目标节点列表之间的最短路径。要计算从源节点到所有可达节点的所有路径，可以使用 Dijkstra 单源算法。

用于 Snowflake 的图形分析的实现基于原始描述，并使用二叉堆作为优先队列。

语法

本节介绍执行 Dijkstra 算法所用的语法。

运行 Dijkstra。

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

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

表 1. 参数
名称	类型	默认值	可选	描述
computePoolSelector	字符串	`不适用`	否	用于运行介数中心性作业的计算池选择器。
configuration	映射	`{}`	否	图项目、算法计算和结果回写配置。

配置映射包含以下三个条目。

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

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

表 3. 计算配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`'total_cost'`	是	将写回 Snowflake 数据库的关系属性。
mutateRelationshipType	字符串	`'PATH'`	是	用于写回 Snowflake 数据库的关系类型。
sourceNode	整数或字符串	`不适用`	否	源节点标识符。
sourceNodeTable	字符串	`不适用`	否	用于映射源节点标识符的表。
targetNode	整数或字符串	`不适用`	否	目标节点标识符。
targetNodeTable	字符串	`不适用`	否	用于映射目标节点标识符的表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将运行无权重计算。

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

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

示例

现在我们将探讨如何将 Dijkstra 应用于道路网络。

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

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.ROADS (SOURCENODEID STRING, TARGETNODEID STRING, COST DOUBLE);
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 关系属性表示。

在以下示例中，我们将演示如何使用此图应用 Dijkstra 最短路径算法。

运行作业

运行 Dijkstra 作业涉及三个步骤：投影、计算和写入。

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

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

表 5. 结果
作业 ID	作业开始时间	作业结束时间	作业结果
job_cec5b6b71a2d4d8dad94f4a653422d63	2025-05-06 10:09:49.579000	2025-05-06 10:09:58.703000	{ "dijkstra_1": { "computeMillis": 13, "configuration": { "concurrency": 6, "jobId": "68ba12d8-108a-4486-b2b4-326961f4efda", "logProgress": true, "mutateRelationshipType": "PATH", "nodeLabels": [ "" ], "relationshipTypes": [ "" ], "relationshipWeightProperty": "COST", "sourceNode": "A", "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS", "sudo": false, "targetNode": 4, "targetNodes": [] }, "mutateMillis": 0, "postProcessingMillis": 0, "preProcessingMillis": 10 }, "project_1": { "graphName": "snowgraph", "nodeCount": 6, "nodeMillis": 393, "relationshipCount": 9, "relationshipMillis": 419, "totalMillis": 812 }, "write_relationship_type_1": { "exportMillis": 1725, "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS", "relationshipProperty": "[SOURCENODEID, TARGETNODEID, NODEIDS, NODELABELS, COSTS, TOTALCOST]", "relationshipType": "PATH", "relationshipsExported": 0 } }

表 5. 结果

作业 ID

作业开始时间

作业结束时间

作业结果

job_cec5b6b71a2d4d8dad94f4a653422d63

2025-05-06 10:09:49.579000

2025-05-06 10:09:58.703000

{
  "dijkstra_1": {
    "computeMillis": 13,
    "configuration": {
      "concurrency": 6,
      "jobId": "68ba12d8-108a-4486-b2b4-326961f4efda",
      "logProgress": true,
      "mutateRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": "A",
      "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS",
      "sudo": false,
      "targetNode": 4,
      "targetNodes": []
    },
    "mutateMillis": 0,
    "postProcessingMillis": 0,
    "preProcessingMillis": 10
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeMillis": 393,
    "relationshipCount": 9,
    "relationshipMillis": 419,
    "totalMillis": 812
  },
  "write_relationship_type_1": {
    "exportMillis": 1725,
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS",
    "relationshipProperty": "[SOURCENODEID, TARGETNODEID, NODEIDS, NODELABELS, COSTS, TOTALCOST]",
    "relationshipType": "PATH",
    "relationshipsExported": 0
  }
}

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

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PATHS;

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

表 6. 结果
源节点 ID	目标节点 ID	节点 ID	节点标签	成本	总成本
A	E	["A", "B", "D", "E"]	["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]	[0, 50, 90, 120]	120

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