6.5.2. Shortest Path

This section describes the Shortest Path algorithm in the Neo4j Graph Data Science library.

The Shortest Path algorithm calculates the shortest (weighted) path between a pair of nodes. In this category, Dijkstra’s algorithm is the most well known. It is a real time graph algorithm, and can be used as part of the normal user flow in a web or mobile application.

This algorithm is in the alpha tier. For more information on algorithm tiers, see Chapter 6, Algorithms.

This section includes:

6.5.2.1. History and explanation

Path finding has a long history, and is considered to be one of the classical graph problems; it has been researched as far back as the 19th century. It gained prominence in the early 1950s in the context of ‘alternate routing’, i.e. finding a second shortest route if the shortest route is blocked.

Dijkstra came up with his algorithm in 1956 while trying to come up with something to show off the new ARMAC computers. He needed to find a problem and solution that people not familiar with computing would be able to understand, and designed what is now known as Dijkstra’s algorithm. He later implemented it for a slightly simplified transportation map of 64 cities in the Netherlands.

6.5.2.2. Use-cases - when to use the Shortest Path algorithm

  • Finding directions between physical locations. This is the most common usage, and web mapping tools such as Google Maps use the shortest path algorithm, or a variant of it, to provide driving directions.
  • Social networks can use the algorithm to find the degrees of separation between people. For example, when you view someone’s profile on LinkedIn, it will indicate how many people separate you in the connections graph, as well as listing your mutual connections.

6.5.2.3. Constraints - when not to use the Shortest Path algorithm

Dijkstra 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.2.4. Syntax

The following will run the algorithm and write back results: 

CALL gds.alpha.shortestPath.write(configuration: Map)
YIELD
  // general write return columns
  nodeCount: Integer,
  totalCost: Float

Table 6.379. Parameters
Name Type Default Optional Description

configuration

Map

null

no

Configuration for anonymous graph creation and algorithm-specifics.

Table 6.380. General configuration for algorithm execution on an anonymous graph.
Name Type Default Optional Description

nodeProjection

String, String[] or Map

null

yes

The node projection used for anonymous graph creation via a Native projection.

relationshipProjection

String, String[] or Map

null

yes

The relationship projection used for anonymous graph creation a Native projection.

nodeQuery

String

null

yes

The Cypher query used to select the nodes for anonymous graph creation via a Cypher projection.

relationshipQuery

String

null

yes

The Cypher query used to select the relationships for anonymous graph creation via a Cypher projection.

nodeProperties

String, String[] or Map

null

yes

The node properties to project during anonymous graph creation.

relationshipProperties

String, String[] or Map

null

yes

The relationship properties to project during anonymous graph creation.

concurrency

Integer

4

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'.

readConcurrency

Integer

value of 'concurrency'

yes

The number of concurrent threads used for creating the graph.

writeConcurrency

Integer

value of 'concurrency'

yes

WRITE mode only: The number of concurrent threads used for writing the result.

writeProperty

String

n/a

no

WRITE mode only: The relationship property to which the similarity score is written to.

Table 6.381. Algorithm specific configuration
Name Type Default Optional Description

startNode

Node

null

no

The start node

endNode

Node

null

no

The end node

relationshipWeightProperty

String

null

yes

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

writeProperty

String

'sssp'

yes

The property name written back to the node sequence of the node in the path

Table 6.382. Results
Name Type Description

nodeCount

Integer

The number of nodes considered

totalCost

Float

The sum of all weights along the path

createMillis

Integer

Milliseconds for loading data

computeMillis

Integer

Milliseconds for running the algorithm

writeMillis

Integer

Milliseconds for writing result data back

The following will run the algorithm and stream results: 

CALL gds.alpha.shortestPath.stream(configuration: Map)
YIELD
  // general write return columns
  nodeId: Integer,
  cost: Float

Table 6.383. Parameters
Name Type Default Optional Description

configuration

Map

null

no

Configuration for anonymous graph creation and algorithm-specifics.

Table 6.384. General configuration for algorithm execution on an anonymous graph.
Name Type Default Optional Description

nodeProjection

String, String[] or Map

null

yes

The node projection used for anonymous graph creation via a Native projection.

relationshipProjection

String, String[] or Map

null

yes

The relationship projection used for anonymous graph creation a Native projection.

nodeQuery

String

null

yes

The Cypher query used to select the nodes for anonymous graph creation via a Cypher projection.

relationshipQuery

String

null

yes

The Cypher query used to select the relationships for anonymous graph creation via a Cypher projection.

nodeProperties

String, String[] or Map

null

yes

The node properties to project during anonymous graph creation.

relationshipProperties

String, String[] or Map

null

yes

The relationship properties to project during anonymous graph creation.

concurrency

Integer

4

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'.

readConcurrency

Integer

value of 'concurrency'

yes

The number of concurrent threads used for creating the graph.

writeConcurrency

Integer

value of 'concurrency'

yes

WRITE mode only: The number of concurrent threads used for writing the result.

writeProperty

String

n/a

no

WRITE mode only: The relationship property to which the similarity score is written to.

Table 6.385. Algorithm specific configuration
Name Type Default Optional Description

startNode

Node

null

no

The start node

endNode

Node

null

no

The end node

relationshipWeightProperty

String

null

yes

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

Table 6.386. Results
Name Type Description

nodeId

Integer

Node ID

cost

Float

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

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

Dijkstra Shortest Path

The following will run the algorithm and stream results: 

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.stream({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'cost'
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).name AS name, cost

Table 6.387. Results
Name Cost

A

0

C

50

D

90

E

120

F

160

The quickest route takes us from A to F, via C, D, and E, at a total cost of 160:

  • First, we go from A to C, at a cost of 50.
  • Then, we go from C to D, for an additional 40.
  • Then, from D to E, for an additional 30.
  • Finally, from E to F, for a further 40.

The following will run the algorithm and write back results: 

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.write({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'cost',
  writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost

Table 6.388. Results
nodeCount totalCost

5

160

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.

Set graph:'cypher' in the config: 

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.write({
  nodeQuery:'MATCH(n:Loc) WHERE NOT n.name = "c" RETURN id(n) AS id',
  relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'weight',
  writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost