Dijkstra 单源最短路径

引言

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

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

语法

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

运行 Dijkstra。
CALL Neo4j_Graph_Analytics.graph.dijkstra_single_source(
  '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

字符串

不适用

否

用于映射源节点标识符的表。

relationshipWeightProperty

字符串

空

是

用作权重的关系属性的名称。如果未指定，算法将按未加权运行。
有关以下写入配置的更多详细信息，请参阅写入文档。
表 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_single_source('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. 结果
作业 ID 作业开始 作业结束 作业结果

job_82537e4136794bc da31286a0c8807397

2025-05-06 08:38:55.301000

2025-05-06 08:39:01.830000

 
{
  "dijkstra_single_source_1": {
    "computeMillis": 14,
    "configuration": {
      "concurrency": 6,
      "jobId": "cffa031c-8324-40f7-a940-cecb66f0957b",
      "logProgress": true,
      "mutateRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": "A",
      "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS",
      "sudo": false
    },
    "mutateMillis": 0,
    "postProcessingMillis": 0,
    "preProcessingMillis": 8
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeMillis": 123,
    "relationshipCount": 9,
    "relationshipMillis": 325,
    "totalMillis": 448
  },
  "write_relationship_type_1": {
    "exportMillis": 1619,
    "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. 结果
SOURCENODEID TARGETNODEID NODEIDS NODELABELS 成本 总成本

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（及其标签）的有序列表，以及访问节点的累计成本。这可以在示例图中进行验证。

即使输入图是无向的，写回的关系也始终是有向的。
© . All rights reserved.