Dijkstra Source-Target Shortest Path

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, or between multiple source-target pairs specified in a table. 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

This section covers the syntax used to execute the Dijkstra algorithm.

Run Dijkstra.
CALL Neo4j_Graph_Analytics.graph.dijkstra(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);
1 Compute pool selector.
2 Optional prefix for table references.
3 Project config.
4 Compute config.
5 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 Dijkstra Source-Target 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

sourceNode

Integer or String

n/a

no1

The source node identifier.

sourceNodeTable

String

n/a

no1

A table for mapping the source node identifier.

targetNode

Integer or String

n/a

no1

The target node identifier.

targetNodeTable

String

n/a

no1

A table for mapping the target node identifier.

targetNodes

List of Integers or Strings

n/a

no1

List of target nodes identifiers.

targetNodesTable

String

n/a

no1

A table for mapping the target nodes identifiers.

sourceTargetNodePairsTable

String

n/a

no1

A table containing multiple source-target node pairs with columns SOURCENODEID and TARGETNODEID. When specified, the algorithm runs for all pairs in the table, and sourceNode/targetNode are ignored.

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.

relationshipWeightProperty

String

null

yes

Name of the relationship property to use as weights. If unspecified, the algorithm runs unweighted.

1 Source-target pairs must be specified in one of the following three ways:

  1. Using sourceNode, sourceNodeTable, and targetNode, targetNodeTable for a single source-target pair.

  2. Using sourceNode, sourceNodeTable, and targetNodes, targetNodesTable for a single source with multiple targets.

  3. Using sourceTargetNodePairsTable, sourceNodeTable, and targetNodeTable for multiple source-target pairs from a table.

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

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', {
    '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'
    }]
});
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": 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
  }
}

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 NODEIDS NODELABELS COSTS TOTALCOST

A

E

["A", "B", "D", "E"]

["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]

[0, 50, 90, 120]

120

The result shows the total cost of the shortest path between node A and node E. It also shows an ordered list of node ids (and their labels) 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.

In the following example we will demonstrate the use of the Dijkstra Shortest Path algorithm using this graph for one source node and list of target nodes.

The following will run the algorithm, and write results back to your tables:
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',
        'targetNodes': ['E', 'C'],
        'targetNodesTable': 'LOCATIONS',
        'relationshipWeightProperty': 'COST'
    },
    'write': [{
        'sourceLabel': 'LOCATIONS',
        'targetLabel': 'LOCATIONS',
        'outputTable': 'PATHS'
    }]
});

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 7. Results
SOURCENODEID TARGETNODEID NODEIDS NODELABELS COSTS TOTALCOST

A

E

["A", "B", "D", "E"]

["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]

[0, 50, 90, 120]

120

A

C

["A", "C"]

["LOCATIONS", "LOCATIONS"]

[0, 50]

50

The result shows the total cost of the shortest path between node A and node E and nodes A and C.

Run job with source-target pairs from a table

The Dijkstra algorithm can process multiple source-target pairs in a single execution by using the sourceTargetNodePairsTable parameter. This is particularly useful for batch processing scenarios where you need to find shortest paths between many different node pairs.

First, create a table containing the source-target node pairs:

Create and populate a pairs table:
CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.NODE_PAIRS (
    SOURCENODEID VARCHAR,
    TARGETNODEID VARCHAR
);

INSERT INTO EXAMPLE_DB.DATA_SCHEMA.NODE_PAIRS VALUES
    ('A', 'E'),
    ('B', 'F'),
    ('C', 'D');

The pairs table must contain exactly two columns:

  • SOURCENODEID: The source node identifier

  • TARGETNODEID: The target node identifier

The data types of these columns must match the node identifiers in your graph.

Run the algorithm with source-target pairs from a table:
CALL Neo4j_Graph_Analytics.graph.dijkstra('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'LOCATIONS' ],
        'relationshipTables': {
            'ROADS': {
                'sourceTable': 'LOCATIONS',
                'targetTable': 'LOCATIONS'
            }
        }
    },
    'compute': {
        'sourceTargetNodePairsTable': 'NODE_PAIRS',
        'sourceNodeTable': 'LOCATIONS',
        'targetNodeTable': 'LOCATIONS',
        'relationshipWeightProperty': 'COST'
    },
    'write': [{
        'sourceLabel': 'LOCATIONS',
        'targetLabel': 'LOCATIONS',
        'outputTable': 'MULTIPLE_PATHS'
    }]
});

When using sourceTargetNodePairsTable:

  • The sourceNode and targetNode parameters are ignored

  • The algorithm reads all rows from the specified table

  • For each row, it computes the shortest path from SOURCENODEID to TARGETNODEID

  • All results are written to the same output table

  • The rows in the result table follow the same order of the source-target pairs table, however there will only be a result if a path between the two nodes exists

  • The same projected graph is used for all computations

  • All individual results will be kept in memory before any results are written to the result table

Query the results:
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PATHS_MULTIPLE ORDER BY SOURCENODEID, TARGETNODEID;
Table 8. Results for multiple pairs
SOURCENODEID TARGETNODEID NODEIDS NODELABELS COSTS TOTALCOST

A

E

["A", "B", "D", "E"]

["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]

[0, 50, 90, 120]

120

B

F

["B", "D", "E", "F"]

["LOCATIONS", "LOCATIONS", "LOCATIONS", "LOCATIONS"]

[0, 40, 70, 110]

110

C

D

["C", "D"]

["LOCATIONS", "LOCATIONS"]

[0, 40]

40

The output table contains one row for each source-target pair from the pairs table, showing the shortest path and its total cost.