Yen's K-Shortest Paths Algorithm
Introduction
Yen's algorithm finds up to k paths from a source node to a target node, in order of total edge weight, shortest first. A path never visits the same node twice. When fewer than k such paths exist, the result holds all of them.
Use it to find alternatives to the shortest path, such as backup routes. The program follows edges in their stored direction only. Edge weights must be zero or more.
Run Yen's algorithm from Cypher with CALL algo.shortestpath.yenK, or from Gremlin with LocalYenKShortestPathProgram. See Shortest Paths for how to run it, the output fields, the arguments shared by all shortest path algorithms, and sizing guidance.
Query Examples
Up to three paths between two nodes
The three shortest paths from marko (person[v1]) to lop (software[v3]) in the Modern example graph:
CALL algo.shortestpath.yenK({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight',
sourceNode: 'person[v1]',
targetNode: 'software[v3]',
k: 3
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight
Output:
graph.program(
LocalYenKShortestPathProgram.build()
.vertices("person", "software")
.edges("knows", "created")
.weightProperty("weight")
.source("person[v1]")
.sink("software[v3]")
.k(3)
.create()
).submitAndGetLocal().getMapResult()
Only two paths exist, so the result has two:
[
{
"vertexList": ["person[v1]", "software[v3]"],
"edgeList": ["created[e9]"],
"edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
"weight": 0.4
},
{
"vertexList": ["person[v1]", "person[v4]", "software[v3]"],
"edgeList": ["knows[e8]", "created[e11]"],
"edgeResultList": [
{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
{"id": "created[e11]", "from": "person[v4]", "to": "software[v3]"}
],
"weight": 1.4
}
]
Adding a cost to every edge
fixedPenalty adds the same number to the weight of every edge, which favors paths with fewer edges. With a penalty of 1.0, each edge in the example above costs one more:
CALL algo.shortestpath.yenK({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight',
fixedPenalty: 1.0,
sourceNode: 'person[v1]',
targetNode: 'software[v3]',
k: 3
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight
Output:
graph.program(
LocalYenKShortestPathProgram.build()
.vertices("person", "software")
.edges("knows", "created")
.weightProperty("weight")
.fixedPenalty(1.0)
.source("person[v1]")
.sink("software[v3]")
.k(3)
.create()
).submitAndGetLocal().getMapResult()
Output:
[
{
"vertexList": ["person[v1]", "software[v3]"],
"edgeList": ["created[e9]"],
"edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
"weight": 1.4
},
{
"vertexList": ["person[v1]", "person[v4]", "software[v3]"],
"edgeList": ["knows[e8]", "created[e11]"],
"edgeResultList": [
{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
{"id": "created[e11]", "from": "person[v4]", "to": "software[v3]"}
],
"weight": 3.4
}
]
Excluding a node
excludeVertexIds leaves nodes and their edges out of the search. Without josh (person[v4]), only the direct path is left:
CALL algo.shortestpath.yenK({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight',
sourceNode: 'person[v1]',
targetNode: 'software[v3]',
k: 3,
excludeNodeIds: ['person[v4]']
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight
Output:
Parameters
| Cypher argument | Gremlin method | Description | Required | Default Value |
|---|---|---|---|---|
sourceNode |
source(String id) |
The ID of the node to start from | Yes | |
targetNode |
sink(String id) |
The ID of the target node | Yes | |
k |
k(int k) |
The maximum number of paths to return. Must be greater than 0 | No in Cypher. Yes in Gremlin | 1 in Cypher |
relationshipWeightProperty |
weightProperty(String name) |
The edge property to use as the weight | Yes |
The common arguments also apply.
Each path search takes longer than a single shortest path search, and the time grows with k. On a large graph, keep k small and limit the labels with labels and relationshipTypes in Cypher, or vertices(...) and edges(...) in Gremlin.