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

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

The following will run the algorithm and write back results:
CALL gds.alpha.shortestPath.deltaStepping.write(configuration: Map)
YIELD nodeCount, loadDuration, evalDuration, writeDuration
Table 1. Configuration
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.

Table 2. Results
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

The following will run the algorithm and stream results:
CALL gds.alpha.shortestPath.deltaStepping.stream(configuration: Map)
YIELD nodeId, distance
Table 3. Parameters
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.

Table 4. Results
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

sssp
The following will create a sample graph:
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

The following will run the algorithm and stream results:
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
Table 5. Results
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.

The following will run the algorithm and write back results:
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
Table 6. Results
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
Table 7. Results
nodeCount

5