Yen’s Shortest Path algorithm

Introduction

Yen’s Shortest Path algorithm computes a number of shortest paths between two nodes. The algorithm is often referred to as Yen’s k-Shortest Path algorithm, where k is the number of shortest paths to compute. The algorithm supports weighted graphs with positive relationship weights. It also respects parallel relationships between the same two nodes when computing multiple shortest paths.

For k = 1, the algorithm behaves exactly like Dijkstra’s shortest path algorithm and returns the shortest path. For k = 2, the algorithm returns the shortest path and the second shortest path between the same source and target node. Generally, for k = n, the algorithm computes at most n paths which are discovered in the order of their total cost.

The GDS implementation is based on the original description. For the actual path computation, Yen’s algorithm uses Dijkstra’s shortest path algorithm. The algorithm makes sure that an already discovered shortest path will not be traversed again.

The algorithm implementation is parallelized, but limited by the number of nodes in source-target paths. If these paths are expected to have small length (i.e., a few new nodes) setting a high value for concurrency is discouraged as some of the cores might be left unutilized.

Syntax

This section covers the syntax used to execute the Yen’s shortest path algorithm algorithm.

Run Yen’s shortest path algorithm.
CALL Neo4j_Graph_Analytics.graph.yens(
  '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 Yen’s shortest path algorithm 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

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.

k

Integer

n/a

no

The number of shortest paths to compute between source and target node.

resultProperty

String

'total_cost'

yes

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

resultRelationshipType

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.
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 Yen’s shortest path algorithm to a road network.

Visualization of the example graph 
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 Yen’s shortest path algorithm Shortest Path algorithm using this graph.

Run job

Running a Yen’s shortest path algorithm 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.yens('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'LOCATIONS' ],
        'relationshipTables': {
            'ROADS': {
                'sourceTable': 'LOCATIONS',
                'targetTable': 'LOCATIONS'
            }
        }
    },
    'compute': {
        'sourceNode': 'A',
        'sourceNodeTable': 'LOCATIONS',
        'targetNode': 'E',
        'k': 3,
        'targetNodeTable': 'LOCATIONS',
        'relationshipWeightProperty': 'COST'
    },
    'write': [{
        'sourceLabel': 'LOCATIONS',
        'targetLabel': 'LOCATIONS',
        'outputTable': 'PATHS'
    }]
});
Table 5. Results
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_8fde6ff409b14e32946625921a264811

SUCCESS

2026-03-16 21:56:45.771000

2026-03-16 21:56:53.839000

 
{
  "yens_1": {
    "computeMillis": 79,
    "configuration": {
      "concurrency": 6,
      "resultRelationshipType": "PATH",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "relationshipWeightProperty": "COST",
      "sourceNode": "A",
      "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.LOCATIONS",
      "targetNode": "E",
    }
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeLabels": ...,
    "nodeMillis": 265,
    "relationshipCount": 9,
    "relationshipMillis": 741,
    "relationshipTypes": ...,
    "totalMillis": 1006
  },
  "write_relationship_type_1": {
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PATHS",
    "relationshipProperty": "[SOURCENODEID, TARGETNODEID, NODEIDS, NODELABELS, COSTS, TOTALCOST]",
    "relationshipType": "PATH",
    "rowsWritten": 3,
    "writeMillis": 2869
  }
}

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

A

E

["A", "C", "D", "E"]

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

[0, 50, 90, 120]

120

A

E

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

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

[0, 100, 130]

130

The result shows the total cost of the shortest path between node A and node E. The first two paths have the same total cost, however the first one traversed from A to D via the B node, while the second traversed via the C node. The third path has a higher total cost as it goes directly from A to D using the relationship with a cost of 100, whereas the detours via B and C for the first two paths costs 50 each. This can be verified in the example graph.