Skip to content

Dijkstra's Algorithm

Introduction

Dijkstra's algorithm finds the path with the lowest total edge weight from a source node. With a sink, it returns the shortest path to that node. Without one, it returns the shortest path to every node the source can reach.

Edge weights must be zero or more. A negative weight fails the run with Negative edge weight not allowed. For negative weights, use Bellman-Ford.

Run Dijkstra's algorithm from Cypher with CALL algo.shortestpath.dijkstra, or from Gremlin with LocalDijkstraShortestPathProgram. See Shortest Paths for how to run it, the output fields, the arguments shared by all shortest path algorithms, and sizing guidance.

Query Examples

The examples use the Modern example graph, where the knows and created edges have a weight property.

Shortest path between two nodes

The shortest path from marko (person[v1]) to ripple (software[v5]):

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]',
    targetNode: 'software[v5]'
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight

Output:

[
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "weight": 2.0
  }
]
graph.program(
  LocalDijkstraShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .sink("software[v5]")
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "edgeResultList": [
      {"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
      {"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}
    ],
    "weight": 2.0
  }
]

Shortest paths to every reachable node

Without a sink, the program returns one path for each node marko can reach:

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]'
    }) 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[v2]"],
    "edgeList": ["knows[e7]"],
    "weight": 0.5
  },
  {
    "vertexList": ["person[v1]", "person[v4]"],
    "edgeList": ["knows[e8]"],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "weight": 2.0
  }
]
graph.program(
  LocalDijkstraShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "person[v4]"],
    "edgeList": ["knows[e8]"],
    "edgeResultList": [{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"}],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v1]", "person[v2]"],
    "edgeList": ["knows[e7]"],
    "edgeResultList": [{"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"}],
    "weight": 0.5
  },
  {
    "vertexList": ["person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e8]", "created[e10]"],
    "edgeResultList": [
      {"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
      {"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}
    ],
    "weight": 2.0
  },
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
    "weight": 0.4
  }
]

peter (person[v6]) is missing because no edge leads from marko to him.

Ignoring edge direction

With asUndirected(true), a path can follow an edge in either direction. The shortest path from ripple (software[v5]) to peter (person[v6]):

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'software[v5]',
    targetNode: 'person[v6]',
    undirected: true
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight

Output:

[
  {
    "vertexList": ["software[v5]", "person[v4]", "software[v3]", "person[v6]"],
    "edgeList": ["created[e10]", "created[e11]", "created[e12]"],
    "weight": 1.6
  }
]
graph.program(
  LocalDijkstraShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("software[v5]")
    .sink("person[v6]")
    .asUndirected(true)
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["software[v5]", "person[v4]", "software[v3]", "person[v6]"],
    "edgeList": ["created[e10]", "created[e11]", "created[e12]"],
    "edgeResultList": [
      {"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"},
      {"id": "created[e11]", "from": "person[v4]", "to": "software[v3]"},
      {"id": "created[e12]", "from": "person[v6]", "to": "software[v3]"}
    ],
    "weight": 1.6
  }
]

Excluding an edge

excludeEdgeIds leaves edges out of the search. marko reaches ripple only through the edge knows[e8], so without it there is no path and the result is empty:

CALL algo.shortestpath.dijkstra({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    relationshipWeightProperty: 'weight',
    sourceNode: 'person[v1]',
    targetNode: 'software[v5]',
    excludeRelationshipIds: ['knows[e8]']
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight

Output:

[]
graph.program(
  LocalDijkstraShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .sink("software[v5]")
    .excludeEdgeIds("knows[e8]")
    .create()
).submitAndGetLocal().getMapResult()

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. Without it, the program returns a path to every reachable node No
undirected asUndirected(boolean undirected) Follow edges in both directions No false
relationshipWeightProperty weightProperty(String name) The edge property to use as the weight Yes

The common arguments also apply.