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