6.5.3. 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 Chapter 6, Algorithms.

This section includes:

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

6.5.3.2. Use-cases - when to use the Single Source Shortest Path algorithm

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

6.5.3.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 6.389. Configuration
Name Type Default Optional Description

startNode

Node

null

no

The start node

relationshipWeightProperty

String

null

yes

The property name that contains weight. If null, treats the graph as unweighted. Must be numeric.

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 6.390. 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 6.391. 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

The property name that contains weight. If null, treats the graph as unweighted. Must be numeric.

Table 6.392. Results
Name Type Description

nodeId

Integer

Node ID

distance

Integer

The cost it takes to get from the start node to the specific node.

6.5.3.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);

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 6.393. 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.394. Results
nodeCount

6

Cypher projection

If node label and relationship type are not selective enough to create the graph projection to run the algorithm on, you can use Cypher queries to project your graph. This can also be used to run algorithms on a virtual graph. You can learn more in the Section 4.3, “Cypher projection” section of the manual.

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 6.395. Results
nodeCount

5