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 5, *Algorithms*.

This section includes:

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.

- K-shortest paths algorithm has been used to optimize multiple object tracking by formalizing the motions of targets as flows along the relationships of the spatial graph. Find more in Multiple Object Tracking using K-Shortest Paths Optimization
- K-shortest paths algorithm is used to study alternative routing on road networks and to recommend top k-paths to the user. Find this study in Alternative Routing: k-Shortest Paths with Limited Overlap
- K-shortest paths algorithm has been used as part of Finding Diverse High-Quality Plans for Hypothesis Generation process.

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.

The following will run the algorithm and write back results:

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

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

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
```

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

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

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
```

`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
```

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
```

`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`

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`

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
```