Skip to content

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:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": 0.4
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v3]"],
    "edgeList": ["knows[e8]", "created[e11]"],
    "weight": 1.4
  }
]
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:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": 1.4
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v3]"],
    "edgeList": ["knows[e8]", "created[e11]"],
    "weight": 3.4
  }
]
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:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": 0.4
  }
]
graph.program(
  LocalYenKShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .sink("software[v3]")
    .k(3)
    .excludeVertexIds("person[v4]")
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
    "weight": 0.4
  }
]

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.