Dijkstra Single-Source Shortest Path

Neo4j Graph Analytics for Snowflake is in Public Preview and is not intended for production use.

Introduction

The Dijkstra Shortest Path algorithm computes the shortest path between nodes. The algorithm supports weighted graphs with positive relationship weights. The Dijkstra Single-Source algorithm computes the shortest paths between a source node and all nodes reachable from that node. To compute the shortest path between a source and a target node, Dijkstra Source-Target can be used.

The Graph Analytics for Snowflake implementation is based on the original description and uses a binary heap as priority queue.

Syntax

Run Dijkstra.
CALL Neo4j_Graph_Analytics.graph.dijkstra_single_source(
  'X64_CPU_L',        (1)
  {
    'project': {...}, (2)
    'compute': {...}, (3)
    'write':   {...}  (4)
  }
);
1 Compute pool selector.
2 Project config.
3 Compute config.
4 Write config.
Table 1. Parameters
Name Type Default Optional Description

computePoolSelector

String

n/a

no

The selector for the compute pool on which to run the Betweenness Centrality job.

configuration

Map

{}

no

Configuration for graph project, algorithm compute and result write back.

The configuration map consists of the following three entries.

For more details on below Project configuration, refer to the Project documentation.
Table 2. Project configuration
Name Type

nodeTables

List of node tables.

relationshipTables

Map of relationship types to relationship tables.
Table 3. Compute configuration
Name Type Default Optional Description

mutateProperty

String

'total_cost'

yes

The relationship property that will be written back to the Snowflake database.

mutateRelationshipType

String

'PATH'

yes

The relationship type used for the relationships written back to the Snowflake database.

sourceNode

Integer or String

n/a

no

The source node identifier.

sourceNodeTable

String

n/a

no

A table for mapping the source node identifier.

relationshipWeightProperty

String

null

yes

Name of the relationship property to use as weights. If unspecified, the algorithm runs unweighted.
For more details on below Write configuration, refer to the Write documentation.
Table 4. Write configuration
Name Type Default Optional Description

sourceLabel

String

n/a

no

Node label in the in-memory graph for start nodes of relationships to be written back.

targetLabel

String

n/a

no

Node label in the in-memory graph for end nodes of relationships to be written back.

outputTable

String

n/a

no

Table in Snowflake database to which relationships are written.

relationshipType

String

'PATH'

yes

The relationship type that will be written back to the Snowflake database.

relationshipProperty

String

'total_cost'

yes

The relationship property that will be written back to the Snowflake database.

Examples

Now we will look at how to apply Dijkstra to a road network.

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);

This graph builds a transportation network with roads between locations. Like in the real world, the roads in the graph have different lengths. These lengths are represented by the cost relationship property.

In the following example we will demonstrate the use of the Dijkstra Shortest Path algorithm using this graph.

Run job

Running a Dijkstra job involves the three steps: Project, Compute and Write.

The following will run the algorithm, and write results back to your tables:
CALL Neo4j_Graph_Analytics.graph.dijkstra_single_source('CPU_X64_XS', {
    'project': {
        'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
        'nodeTables': [ 'LOCATIONS' ],
        'relationshipTables': {
            'roads': {
                'sourceTable': 'LOCATIONS',
                'targetTable': 'LOCATIONS'
            }
        }
    },
    'compute': {
        'sourceNode': 'A',
        'sourceNodeTable': 'EXAMPLE_DB.DATA_SCHEMA.LOCATIONS',
        'relationshipWeightProperty': 'COST'
    },
    'write': [{
        'sourceLabel': 'LOCATIONS',
        'targetLabel': 'LOCATIONS',
        'outputTable': 'EXAMPLE_DB.DATA_SCHEMA.PATHS'
    }]
});
Table 5. Results
JOB_ID JOB_START JOB_END JOB_RESULT

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": 2,
      "jobId": "a6e36d81-dbaa-4aee-baf6-7b33a41a3ec0",
      "logProgress": true,
      "mutateRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": 0,
      "sudo": false
    },
    "mutateMillis": 0,
    "postProcessingMillis": 18,
    "preProcessingMillis": 8,
    "relationshipsWritten": 6
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeMillis": 255,
    "relationshipCount": 9,
    "relationshipMillis": 678,
    "totalMillis": 933
  },
  "write_relationship_type_1": {
    "exportMillis": 2009,
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.paths",
    "relationshipProperty": "totalCost",
    "relationshipType": "PATH",
    "relationshipsExported": 6
  }
}

The returned result contains information about the job execution. Additionally, the shortest path(s) have been written back to the Snowflake database. We can query it like so:

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PATHS;

Which shows the computation results as stored in the database:

Table 6. Results
SOURCENODEID TARGETNODEID TOTALCOST

A

A

0.0

A

B

50.0

A

C

50.0

A

D

90.0

A

E

120.0

A

F

160.0

The result shows the total cost of the shortest path between node A and all other reachable nodes in the graph. It also shows ordered lists of node ids that were traversed to find the shortest paths as well as the accumulated costs of the visited nodes. This can be verified in the example graph.

The relationships written are always directed, even if the input graph is undirected.