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

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	Name of the relationship property to use as weights. If unspecified, the algorithm runs 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	Name of the relationship property to use as weights. If unspecified, the algorithm runs 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

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

If node labels and relationship types are not selective enough to project a graph, you can use Cypher queries instead. Cypher projections can also be used to run algorithms on a virtual graph. You can learn more in the Creating graphs using Cypher 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 7. Results
nodeCount
5

Was this page helpful?