7.4.6. The Yen’s K-shortest paths algorithm

This section describes the Yen’s K-shortest paths algorithm in the Neo4j Labs Graph Algorithms library.

Yen’s K-shortest paths algorithm computes single-source K-shortest loopless paths for a graph with non-negative relationship weights.

The Yen’s K-shortest paths algorithm was developed by the Neo4j Labs team and is not officially supported.

This section includes:

7.4.6.1. History and explanation

Algorithm was defined in 1971 by Jin Y. Yen in the research paper Finding the K Shortest Loopless Paths in a Network. Our implementation uses Dijkstra algorithm to find the shortest path and then proceeds to find k-1 deviations of the shortest paths.

7.4.6.2. Use-cases - when to use the Yen’s K-shortest paths algorithm

7.4.6.3. Constraints - when not to use the Yen’s K-shortest paths algorithm

Yen’s K-Shortest paths algorithm does not support negative weights. The algorithm assumes that adding a relationship to a path can never make a path shorter - an invariant that would be violated with negative weights.

7.4.6.4. Yen’s K-shortest paths algorithm sample

yens

The following will create a sample graph: 

MERGE (a:Loc {name:'A'})
MERGE (b:Loc {name:'B'})
MERGE (c:Loc {name:'C'})
MERGE (d:Loc {name:'D'})
MERGE (e:Loc {name:'E'})
MERGE (f:Loc {name:'F'})

MERGE (a)-[:ROAD {cost:50}]->(b)
MERGE (a)-[:ROAD {cost:50}]->(c)
MERGE (a)-[:ROAD {cost:100}]->(d)
MERGE (b)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:80}]->(e)
MERGE (d)-[:ROAD {cost:30}]->(e)
MERGE (d)-[:ROAD {cost:80}]->(f)
MERGE (e)-[:ROAD {cost:40}]->(f);

The following will run the algorithm and stream results: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.kShortestPaths.stream(start, end, 3, 'cost' ,{})

YIELD index, nodeIds, costs
RETURN [node in algo.getNodesById(nodeIds) | node.name] AS places,
       costs,
       reduce(acc = 0.0, cost in costs | acc + cost) AS totalCost

Table 7.77. Results
places costs totalCost

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

[50.0, 40.0, 30.0, 40.0]

160.0

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

[50.0, 40.0, 30.0, 40.0]

160.0

["A", "B", "D", "F"]

[50.0, 40.0, 80.0]

170.0

This procedure doesn’t return paths by default, but we can have it return those by passing in the config path: true.

The following will run the algorithm and stream results, including paths: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.kShortestPaths.stream(start, end, 3, 'cost', {path: true})
YIELD path
RETURN path
LIMIT 1

yens path

The following will run the algorithm and write back results: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.kShortestPaths(start, end, 3, 'cost' ,{})
YIELD resultCount
RETURN resultCount

The following will return all 3 of the shortest path: 

MATCH p=()-[r:PATH_0|:PATH_1|:PATH_2]->() RETURN p LIMIT 25

yens result

The quickest route takes us from A to B, via D and E and is saved as PATH_0. Second quickest path is saved as PATH_1 and third one is saved as`PATH_2`

7.4.6.5. Cypher projection

If node label and relationship type are not selective enough to describe your subgraph to run the algorithm on, you can use Cypher statements to load or project subsets of your graph. This can also be used to run algorithms on a virtual graph. You can learn more in the Section 2.2, “Cypher projection” section of the manual.

Set graph:'cypher' in the config: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.kShortestPaths(start, end, 3, 'cost',{
nodeQuery:'MATCH(n:Loc) WHERE not n.name = "C" RETURN id(n) as id',
relationshipQuery:'MATCH (n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) as source, id(m) as target, r.cost as weight',
graph:'cypher',writePropertyPrefix:'cypher_'})
YIELD resultCount
RETURN resultCount

7.4.6.6. Syntax

The following will run the algorithm and write back results: 

CALL algo.kShortestPaths(startNode:Node, endNode:Node, k:int, weightProperty:String,
    {nodeQuery:'labelName', relationshipQuery:'relationshipName', direction:'OUT', defaultValue:1.0,
    maxDepth:42, write:'true', writePropertyPrefix:'PATH_'})
YIELD resultCount, loadMillis, evalMillis, writeMillis

Table 7.78. Parameters
Name Type Default Optional Description

startNode

node

null

no

The start node

endNode

node

null

no

The end node

weightProperty

string

null

yes

The property name that contains weight. If null, treats the graph as unweighted. Must be numeric.

nodeQuery

string

null

yes

The label to load from the graph. If null, load all nodes

relationshipQuery

string

null

yes

The relationship type to load from the graph. If null, load all nodes

direction

string

both

yes

The relationship direction to load from the graph. If 'both', treats the relationships as undirected

defaultValue

float

null

yes

The default value of the weight in case it is missing or invalid

maxDepth

int

Integer.MAX

yes

The depth of the shortest paths traversal

write

boolean

true

yes

Specifies if the result should be written back as a node property

writePropertyPrefix

string

'PATH_'

yes

The relationship-type prefix written back to the graph

Table 7.79. Results
Name Type Description

resultCount

int

The number of shortest paths results

loadMillis

int

Milliseconds for loading data

evalMillis

int

Milliseconds for running the algorithm

writeMillis

int

Milliseconds for writing result data back

7.4.6.7. Graph type support

The Shortest Path algorithms support the following graph types:

  • ✓ directed, unweighted:

    • direction: 'OUTGOING' or INCOMING, weightProperty: null
  • ✓ directed, weighted

    • direction: 'OUTGOING' or INCOMING, weightProperty: 'cost'
  • ✓ undirected, unweighted

    • direction: 'BOTH', weightProperty: null
  • ✓ undirected, weighted

    • direction: 'BOTH', weightProperty: 'cost'

7.4.6.8. Implementations

algo.kShortestPaths

  • Specify start and end node, find the k-shortest path between them.
  • If initialized with an non-existing weight-property, it will treat the graph as unweighted.