Dijkstra Source-Target 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 Source-Target algorithm computes the shortest path between a source and a list of target nodes. To compute all paths from a source node to all reachable nodes, Dijkstra Single-Source 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(
  '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.

targetNode

Integer or String

n/a

no

The target node identifier.

targetNodeTable

String

n/a

no

A table for mapping the target 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);

We use the tables above as input and project them into an in-memory graph. 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('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',
        'targetNode': 'E',
        'targetNodeTable': '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_cec5b6b71a2d4d8dad94f4a653422d63

2025-05-06 10:09:49.579000

2025-05-06 10:09:58.703000

 
{
  "dijkstra_1": {
    "computeMillis": 14,
    "configuration": {
      "concurrency": 2,
      "jobId": "a3c40e73-dff1-4715-844b-42252d3aa270",
      "logProgress": true,
      "mutateRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": 0,
      "sudo": false,
      "targetNode": 5,
      "targetNodes": []
    },
    "mutateMillis": 0,
    "postProcessingMillis": 9,
    "preProcessingMillis": 8,
    "relationshipsWritten": 1
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeMillis": 460,
    "relationshipCount": 9,
    "relationshipMillis": 1128,
    "totalMillis": 1588
  },
  "write_relationship_type_1": {
    "exportMillis": 2656,
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS",
    "relationshipProperty": "totalCost",
    "relationshipType": "PATH",
    "relationshipsExported": 1
  }
}

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

F

160.0

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