Yen’s algorithm
This section describes the Yen’s Shortest Path algorithm in the Neo4j Graph Data Science library.
1. Introduction
Yen’s Shortest Path algorithm computes a number of shortest paths between two nodes. The algorithm is often referred to as Yen’s kShortest 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 executed using a single thread. Altering the concurrency configuration has no effect.
2. Syntax
This section covers the syntax used to execute the Yen’s algorithm in each of its execution modes. We are describing the named graph variant of the syntax. To learn more about general syntax variants, see Syntax overview.
CALL gds.shortestPath.yens.stream(
graphName: String,
configuration: Map
)
YIELD
index: Integer,
sourceNode: Integer,
targetNode: Integer,
totalCost: Float,
nodeIds: List of Integer,
costs: List of Float,
path: Path
Name  Type  Default  Optional  Description 

graphName 
String 

no 
The name of a graph stored in the catalog. 
configuration 
Map 

yes 
Configuration for algorithmspecifics and/or graph filtering. 
Name  Type  Default  Optional  Description 

String[] 

yes 
Filter the named graph using the given node labels. 

String[] 

yes 
Filter the named graph using the given relationship types. 

Integer 

yes 
The number of concurrent threads used for running the algorithm. 
Name  Type  Default  Optional  Description 

sourceNode 
Integer 

no 
The Neo4j source node or node id. 
targetNode 
Integer 

no 
The Neo4j target node or node id. 
k 
Integer 

yes 
The number of shortest paths to compute between source and target node. 
Name  Type  Description 

index 
Integer 
0based index of the found path. 
sourceNode 
Integer 
Source node of the path. 
targetNode 
Integer 
Target node of the path. 
totalCost 
Float 
Total cost from source to target. 
nodeIds 
List of Integer 
Node ids on the path in traversal order. 
costs 
List of Float 
Accumulated costs for each node on the path. 
path 
Path 
The path represented as Cypher entity. 
The mutate mode creates new relationships in the inmemory graph.
Each relationship represents a path from the source node to the target node.
The total cost of a path is stored via the totalCost
relationship property.
CALL gds.shortestPath.yens.mutate(
graphName: String,
configuration: Map
)
YIELD
relationshipsWritten: Integer,
createMillis: Integer,
computeMillis: Integer,
postProcessingMillis: Integer,
mutateMillis: Integer,
configuration: Map
Name  Type  Default  Optional  Description 

graphName 
String 

no 
The name of a graph stored in the catalog. 
configuration 
Map 

yes 
Configuration for algorithmspecifics and/or graph filtering. 
Name  Type  Default  Optional  Description 

String[] 

yes 
Filter the named graph using the given node labels. 

String[] 

yes 
Filter the named graph using the given relationship types. 

Integer 

yes 
The number of concurrent threads used for running the algorithm. 

mutateRelationshipType 
String 

no 
The relationship type used for the new relationships written to the inmemory graph. 
Name  Type  Default  Optional  Description 

sourceNode 
Integer 

no 
The Neo4j source node or node id. 
targetNode 
Integer 

no 
The Neo4j target node or node id. 
k 
Integer 

yes 
The number of shortest paths to compute between source and target node. 
Name  Type  Description 

createMillis 
Integer 
Milliseconds for creating the graph. 
computeMillis 
Integer 
Milliseconds for running the algorithm. 
postProcessingMillis 
Integer 
Unused. 
mutateMillis 
Integer 
Milliseconds for adding relationships to the inmemory graph. 
relationshipsWritten 
Integer 
The number of relationships that were added. 
configuration 
Map 
The configuration used for running the algorithm. 
The write mode creates new relationships in the Neo4j database.
Each relationship represents a path from the source node to the target node.
Additional path information is stored using relationship properties.
By default, the write mode stores a totalCost
property.
Optionally, one can also store nodeIds
and costs
of intermediate nodes on the path.
CALL gds.shortestPath.yens.write(
graphName: String,
configuration: Map
)
YIELD
relationshipsWritten: Integer,
createMillis: Integer,
computeMillis: Integer,
postProcessingMillis: Integer,
writeMillis: Integer,
configuration: Map
Name  Type  Default  Optional  Description 

graphName 
String 

no 
The name of a graph stored in the catalog. 
configuration 
Map 

yes 
Configuration for algorithmspecifics and/or graph filtering. 
Name  Type  Default  Optional  Description 

String[] 

yes 
Filter the named graph using the given node labels. 

String[] 

yes 
Filter the named graph using the given relationship types. 

Integer 

yes 
The number of concurrent threads used for running the algorithm. Also provides the default value for 'writeConcurrency'. 

Integer 

yes 
The number of concurrent threads used for writing the result to Neo4j. 

writeRelationshipType 
String 

no 
The relationship type used to persist the computed relationships in the Neo4j database. 
Name  Type  Default  Optional  Description 

sourceNode 
Integer 

no 
The Neo4j source node or node id. 
targetNode 
Integer 

no 
The Neo4j target node or node id. 
k 
Integer 

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

yes 
If true, the written relationship has a nodeIds list property. 
writeCosts 
Boolean 

yes 
If true, the written relationship has a costs list property. 
Name  Type  Description 

createMillis 
Integer 
Milliseconds for creating the graph. 
computeMillis 
Integer 
Milliseconds for running the algorithm. 
postProcessingMillis 
Integer 
Unused. 
writeMillis 
Integer 
Milliseconds for writing relationships to Neo4j. 
relationshipsWritten 
Integer 
The number of relationships that were written. 
configuration 
Map 
The configuration used for running the algorithm. 
2.1. Anonymous graphs
It is also possible to execute the algorithm on a graph that is projected in conjunction with the algorithm execution.
In this case, the graph does not have a name, and we call it anonymous.
When executing over an anonymous graph the configuration map contains a graph projection configuration as well as an algorithm configuration.
All execution modes support execution on anonymous graphs, although we only show syntax and modespecific configuration for the write
mode for brevity.
For more information on syntax variants, see Syntax overview.
CALL gds.shortestPath.yens.write(
configuration: Map
)
YIELD
relationshipsWritten: Integer,
ranIterations: Integer,
didConverge: Boolean,
createMillis: Integer,
computeMillis: Integer,
writeMillis: Integer,
configuration: Map
Name  Type  Default  Optional  Description 

nodeProjection 
String, String[] or Map 

yes 
The node projection used for anonymous graph creation via a Native projection. 
relationshipProjection 
String, String[] or Map 

yes 
The relationship projection used for anonymous graph creation a Native projection. 
nodeQuery 
String 

yes 
The Cypher query used to select the nodes for anonymous graph creation via a Cypher projection. 
relationshipQuery 
String 

yes 
The Cypher query used to select the relationships for anonymous graph creation via a Cypher projection. 
nodeProperties 
String, String[] or Map 

yes 
The node properties to project during anonymous graph creation. 
relationshipProperties 
String, String[] or Map 

yes 
The relationship properties to project during anonymous graph creation. 
Integer 

yes 
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. 

readConcurrency 
Integer 

yes 
The number of concurrent threads used for creating the graph. 
Integer 

yes 
The number of concurrent threads used for writing the result to Neo4j. 

writeRelationshipType 
String 

no 
The relationship type used to persist the computed relationships in the Neo4j database. 
Name  Type  Default  Optional  Description 

sourceNode 
Integer 

no 
The Neo4j node id of the source node. 
targetNode 
Integer 

no 
The Neo4j node id of the target node. 
k 
Integer 

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

yes 
Iff true, the written relationship has a nodeIds list property. 
writeCosts 
Boolean 

yes 
Iff true, the written relationship has a costs list property. 
The results are the same as for running write mode with a named graph, see the write mode syntax above.
3. Examples
In this section we will show examples of running the Yen’s algorithm on a concrete graph. The intention is to illustrate what the results look like and to provide a guide in how to make use of the algorithm in a real setting. We will do this on a small transport network graph of a handful nodes connected in a particular pattern. The example graph looks like this:
CREATE (a:Location {name: 'A'}),
(b:Location {name: 'B'}),
(c:Location {name: 'C'}),
(d:Location {name: 'D'}),
(e:Location {name: 'E'}),
(f:Location {name: 'F'}),
(a)[:ROAD {cost: 50}]>(b),
(a)[:ROAD {cost: 50}]>(c),
(a)[:ROAD {cost: 100}]>(d),
(b)[:ROAD {cost: 40}]>(d),
(c)[:ROAD {cost: 40}]>(d),
(c)[:ROAD {cost: 80}]>(e),
(d)[:ROAD {cost: 30}]>(e),
(d)[:ROAD {cost: 80}]>(f),
(e)[:ROAD {cost: 40}]>(f);
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 examples below we will use named graphs and native projections as the norm. However, anonymous graphs and/or Cypher projections can also be used. 
CALL gds.graph.create(
'myGraph',
'Location',
'ROAD',
{
relationshipProperties: 'cost'
}
)
In the following example we will demonstrate the use of the Yen’s Shortest Path algorithm using this graph.
3.1. Memory Estimation
First off, we will estimate the cost of running the algorithm using the estimate
procedure.
This can be done with any execution mode.
We will use the write
mode in this example.
Estimating the algorithm is useful to understand the memory impact that running the algorithm on your graph will have.
When you later actually run the algorithm in one of the execution modes the system will perform an estimation.
If the estimation shows that there is a very high probability of the execution going over its memory limitations, the execution is prohibited.
To read more about this, see Automatic estimation and execution blocking.
For more details on estimate
in general, see Memory Estimation.
MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.write.estimate('myGraph', {
sourceNode: source,
targetNode: target,
k: 3,
relationshipWeightProperty: 'cost',
writeRelationshipType: 'PATH'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
nodeCount  relationshipCount  bytesMin  bytesMax  requiredMemory 

6 
9 
1008 
1008 
"1008 Bytes" 
3.2. Stream
In the stream
execution mode, the algorithm returns the shortest path for each sourcetargetpair.
This allows us to inspect the results directly or postprocess them in Cypher without any side effects.
For more details on the stream
mode in general, see Stream.
MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.stream('myGraph', {
sourceNode: source,
targetNode: target,
k: 3,
relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
index,
gds.util.asNode(sourceNode).name AS sourceNodeName,
gds.util.asNode(targetNode).name AS targetNodeName,
totalCost,
[nodeId IN nodeIds  gds.util.asNode(nodeId).name] AS nodeNames,
costs,
nodes(path) as path
ORDER BY index
index  sourceNodeName  targetNodeName  totalCost  nodeNames  costs  path 

0 
"A" 
"F" 
160.0 
[A, B, D, E, F] 
[0.0, 50.0, 90.0, 120.0, 160.0] 
[Node[0], Node[1], Node[3], Node[4], Node[5]] 
1 
"A" 
"F" 
160.0 
[A, C, D, E, F] 
[0.0, 50.0, 90.0, 120.0, 160.0] 
[Node[0], Node[2], Node[3], Node[4], Node[5]] 
2 
"A" 
"F" 
170.0 
[A, B, D, F] 
[0.0, 50.0, 90.0, 170.0] 
[Node[0], Node[1], Node[3], Node[5]] 
The result shows the three shortest paths between node A
and node F
.
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 D
to F
using the relationship with a cost of 80
, whereas the detour via E
for the first two paths costs 70
.
This can be verified in the example graph.
Cypher Path objects can be returned by the path
return field.
The Path objects contain the node objects and virtual relationships which have a cost
property.
3.3. Mutate
The mutate
execution mode updates the named graph with new relationships.
Each new relationship represents a path from source node to target node.
The relationship type is configured using the mutateRelationshipType
option.
The total path cost is stored using the totalCost
property.
The mutate
mode is especially useful when multiple algorithms are used in conjunction.
For more details on the mutate
mode in general, see Mutate.
mutate
mode:MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.mutate('myGraph', {
sourceNode: source,
targetNode: target,
k: 3,
relationshipWeightProperty: 'cost',
mutateRelationshipType: 'PATH'
})
YIELD relationshipsWritten
RETURN relationshipsWritten
relationshipsWritten 

3 
After executing the above query, the inmemory graph will be updated with a new relationship of type PATH
.
The new relationship will store a single property totalCost
.
3.4. Write
The write
execution mode updates the Neo4j database with new relationships.
Each new relationship represents a path from source node to target node.
The relationship type is configured using the writeRelationshipType
option.
The total path cost is stored using the totalCost
property.
The intermediate node ids are stored using the nodeIds
property.
The accumulated costs to reach an intermediate node are stored using the costs
property.
For more details on the write
mode in general, see Write.
write
mode:MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.yens.write('myGraph', {
sourceNode: source,
targetNode: target,
k: 3,
relationshipWeightProperty: 'cost',
writeRelationshipType: 'PATH',
writeNodeIds: true,
writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten
relationshipsWritten 

3 
The above query will write a single relationship of type PATH
back to Neo4j.
The relationship stores three properties describing the path: totalCost
, nodeIds
and costs
.
Was this page helpful?