6.5.6. Yen’s K-Shortest Paths

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

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

This algorithm is in the alpha tier. For more information on algorithm tiers, see Chapter 6, Algorithms.

This section includes:

6.5.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.

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

6.5.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.

6.5.6.4. Syntax

The following will run the algorithm and write back results: 

CALL gds.alpha.kShortestPaths.write(configuration: Map)
YIELD resultCount, createMillis, computeMillis, writeMillis

Table 6.403. Configuration
Name Type Default Optional Description

startNode

Node

n/a

no

The start node

endNode

Node

n/a

no

The end node

k

Integer

n/a

no

The number of paths to return.

relationshipWeightProperty

String

null

yes

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

maxDepth

Integer

Integer.MAX

yes

The depth of the shortest paths traversal.

writePropertyPrefix

String

'PATH_'

yes

The relationship-type prefix written back to the graph.

relationshipWriteProperty

String

'weight'

yes

The relationship property written back to the graph.

Table 6.404. Results
Name Type Description

resultCount

Integer

The number of shortest paths results

createMillis

Integer

Milliseconds for loading data

computeMillis

Integer

Milliseconds for running the algorithm

writeMillis

Integer

Milliseconds for writing result data back

The following will run the algorithm and stream the results: 

CALL gds.alpha.kShortestPaths.stream(configuration: Map)
YIELD index, sourceNodeId, targetNodeId, nodeIds, costs, path

Table 6.405. Configuration
Name Type Default Optional Description

startNode

Node

null

no

The start node

endNode

Node

null

no

The end node

k

Integer

N/A

no

The number of paths to return.

relationshipWeightProperty

String

null

yes

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

maxDepth

Integer

Integer.MAX

yes

The depth of the shortest paths traversal.

path

Boolean

false

yes

Whether or not to include string representation of the path with the result.

Table 6.406. Results
Name Type Description

index

Integer

Index of the result

startNodeId

Integer

The start node id

targetNodeId

Integer

The end node id

nodeIds

Integer[]

List containing the node ids that form the path.

costs

Float[]

List containing the costs.

path

String

Optional string representation of the path.

6.5.6.5. Yen’s K-shortest paths algorithm sample

yens

The following will create a sample graph: 

CREATE (a:Loc {name:'A'}),
      (b:Loc {name:'B'}),
      (c:Loc {name:'C'}),
      (d:Loc {name:'D'}),
      (e:Loc {name:'E'}),
      (f:Loc {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);

The following will run the algorithm and stream results: 

MATCH (start:Loc{name: 'A'}), (end:Loc{name: 'F'})
CALL gds.alpha.kShortestPaths.stream({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost'
    }
  },
  startNode: start,
  endNode: end,
  k: 3,
  relationshipWeightProperty: 'cost'
})
YIELD index, nodeIds, costs
RETURN [node IN gds.util.asNodes(nodeIds) | node.name] AS places,
       costs,
       reduce(acc = 0.0, cost IN costs | acc + cost) AS totalCost

Table 6.407. 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 gds.alpha.kShortestPaths.stream({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost'
    }
  },
  startNode: start,
  endNode: end,
  k: 3,
  relationshipWeightProperty: '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 gds.alpha.kShortestPaths.write({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost'
    }
  },
  startNode: start,
  endNode: end,
  k: 3,
  relationshipWeightProperty: 'cost'
})
YIELD resultCount
RETURN resultCount

Table 6.408. Results
resultCount

3

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`

6.5.6.6. Cypher projection

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

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.kShortestPaths.write({
  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',
  startNode: start,
  endNode: end,
  k: 3,
  relationshipWeightProperty: 'cost',
  writePropertyPrefix: 'cypher_'
})
YIELD resultCount
RETURN resultCount