Single Source Shortest Path
This section describes the Single Source Shortest Path algorithm in the Neo4j Graph Data Science library.
The Single Source Shortest Path (SSSP) algorithm calculates the shortest (weighted) path from a node to all other nodes in the graph.
This algorithm is in the alpha tier. For more information on algorithm tiers, see Algorithms.
1. History and explanation
SSSP came into prominence at the same time as the shortest path algorithm and Dijkstra’s algorithm can act as an implementation for both problems.
We implement a delta-stepping algorithm that has been shown to outperform Dijkstra’s.
2. Use-cases - when to use the Single Source Shortest Path algorithm
-
Open Shortest Path First is a routing protocol for IP networks. It uses Dijkstra’s algorithm to help detect changes in topology, such as link failures, and come up with a new routing structure in seconds.
3. Constraints - when not to use the Single Source Shortest Path algorithm
Delta stepping 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.
4. Syntax
CALL gds.alpha.shortestPath.deltaStepping.write(configuration: Map)
YIELD nodeCount, loadDuration, evalDuration, writeDuration
Name | Type | Default | Optional | Description |
---|---|---|---|---|
startNode |
Node |
null |
no |
The start node |
relationshipWeightProperty |
String |
null |
yes |
If set, the values stored at the given property are used as relationship weights during the computation. If not set, the graph is considered unweighted. |
delta |
Float |
null |
yes |
The grade of concurrency to use. |
writeProperty |
String |
'sssp' |
yes |
The property name written back to the node sequence of the node in the path. The property contains the cost it takes to get from the start node to the specific node. |
Name | Type | Description |
---|---|---|
nodeCount |
Integer |
The number of nodes considered |
loadDuration |
Integer |
Milliseconds for loading data |
evalDuration |
Integer |
Milliseconds for running the algorithm |
writeDuration |
Integer |
Milliseconds for writing result data back |
CALL gds.alpha.shortestPath.deltaStepping.stream(configuration: Map)
YIELD nodeId, distance
Name | Type | Default | Optional | Description |
---|---|---|---|---|
startNode |
Node |
null |
no |
The start node |
delta |
Float |
null |
no |
The grade of concurrency to use. |
relationshipWeightProperty |
String |
null |
yes |
If set, the values stored at the given property are used as relationship weights during the computation. If not set, the graph is considered unweighted. |
Name | Type | Description |
---|---|---|
nodeId |
Integer |
Node ID |
distance |
Integer |
The cost it takes to get from the start node to the specific node. |
5. Single Source Shortest Path algorithm sample

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);
5.1. Delta stepping algorithm
MATCH (n:Loc {name: 'A'})
CALL gds.alpha.shortestPath.deltaStepping.stream({
nodeProjection: 'Loc',
relationshipProjection: {
ROAD: {
type: 'ROAD',
properties: 'cost'
}
},
startNode: n,
relationshipWeightProperty: 'cost',
delta: 3.0
})
YIELD nodeId, distance
RETURN gds.util.asNode(nodeId).name AS Name, distance AS Cost
Name | Cost |
---|---|
"A" |
0.0 |
"B" |
50.0 |
"C" |
50.0 |
"D" |
90.0 |
"E" |
120.0 |
"F" |
160.0 |
The above table shows the cost of going from A to each of the other nodes, including itself at a cost of 0.
MATCH (n:Loc {name: 'A'})
CALL gds.alpha.shortestPath.deltaStepping.write({
nodeProjection: 'Loc',
relationshipProjection: {
ROAD: {
type: 'ROAD',
properties: 'cost'
}
},
startNode: n,
relationshipWeightProperty: 'cost',
delta: 3.0,
writeProperty: 'sssp'
})
YIELD nodeCount
RETURN nodeCount
nodeCount |
---|
6 |
5.1.1. Cypher projection
MATCH (start:Loc {name: 'A'})
CALL gds.alpha.shortestPath.deltaStepping.write({
nodeQuery:'MATCH(n:Loc) WHERE not n.name = "C" RETURN id(n) AS id',
relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) WHERE not (n.name = "C" OR m.name = "C") RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
startNode: start,
relationshipWeightProperty: 'weight',
delta: 3.0,
writeProperty: 'sssp'
})
YIELD nodeCount
RETURN nodeCount
nodeCount |
---|
5 |
Was this page helpful?