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.
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. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
computePoolSelector |
String |
|
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. |
Name | Type |
---|---|
nodeTables |
List of node tables. |
relationshipTables |
Map of relationship types to relationship tables. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
mutateProperty |
String |
|
yes |
The relationship property that will be written back to the Snowflake database. |
mutateRelationshipType |
String |
|
yes |
The relationship type used for the relationships written back to the Snowflake database. |
sourceNode |
Integer or String |
|
no1 |
The source node identifier. |
sourceNodeTable |
String |
|
no |
A table for mapping the source node identifier. |
targetNode |
Integer or String |
|
no1 |
The target node identifier. |
targetNodeTable |
String |
|
no |
A table for mapping the target node identifier. |
sourceTargetNodePairsTable |
String |
|
yes2 |
A table containing multiple source-target node pairs with columns |
relationshipWeightProperty |
String |
|
yes |
Name of the relationship property to use as weights. If unspecified, the algorithm runs unweighted. |
1 Required when sourceTargetNodePairsTable
is not specified.
2 When specified, sourceNode
and targetNode
are ignored, and the algorithm processes all source-target pairs from the table.
For more details on below Write configuration, refer to the Write documentation. |
Name | Type | Default | Optional | Description |
---|---|---|---|---|
sourceLabel |
String |
|
no |
Node label in the in-memory graph for start nodes of relationships to be written back. |
targetLabel |
String |
|
no |
Node label in the in-memory graph for end nodes of relationships to be written back. |
outputTable |
String |
|
no |
Table in Snowflake database to which relationships are written. |
relationshipType |
String |
|
yes |
The relationship type that will be written back to the Snowflake database. |
relationshipProperty |
String |
|
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.
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'
}]
});
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:
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.
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 OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.NODE_PAIRS (
SOURCENODEID STRING,
TARGETNODEID STRING
);
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.
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
andtargetNode
parameters are ignored -
The algorithm reads all rows from the specified table
-
For each row, it computes the shortest path from
SOURCENODEID
toTARGETNODEID
-
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
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PATHS_MULTIPLE ORDER BY SOURCENODEID, TARGETNODEID;
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.