9.4.2. The Shortest Path algorithm

This section describes the Shortest Path algorithm in the Neo4j Labs Graph Algorithms 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.

The Shortest Path algorithm was developed by the Neo4j Labs team and is not officially supported.

This section includes:

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

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

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

9.4.2.4. Shortest Path algorithm sample

sssp

The following will create a sample graph: 

MERGE (a:Loc {name:'A'})
MERGE (b:Loc {name:'B'})
MERGE (c:Loc {name:'C'})
MERGE (d:Loc {name:'D'})
MERGE (e:Loc {name:'E'})
MERGE (f:Loc {name:'F'})

MERGE (a)-[:ROAD {cost:50}]->(b)
MERGE (a)-[:ROAD {cost:50}]->(c)
MERGE (a)-[:ROAD {cost:100}]->(d)
MERGE (b)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:80}]->(e)
MERGE (d)-[:ROAD {cost:30}]->(e)
MERGE (d)-[:ROAD {cost:80}]->(f)
MERGE (e)-[:ROAD {cost:40}]->(f);

The Dijkstra Shortest Path algorithm

The following will run the algorithm and stream results: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath.stream(start, end, 'cost')
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost

The following will run the algorithm and write back results: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost',{write:true,writeProperty:'sssp'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost

Table 9.63. 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.

9.4.2.5. Cypher projection

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

Set graph:'cypher' in the config: 

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost',{
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',
graph:'cypher'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost

9.4.2.6. Syntax

The following will run the algorithm and write back results: 

CALL algo.shortestPath(startNode:Node, endNode:Node, weightProperty:String
    {nodeQuery:'labelName', relationshipQuery:'relationshipName', defaultValue:1.0, write:'true', writeProperty:'sssp', direction:'OUTGOING'})
YIELD nodeCount, totalCost, loadMillis, evalMillis, writeMillis

Table 9.64. Parameters
Name Type Default Optional Description

startNode

node

null

no

The start node

endNode

node

null

no

The end node

weightProperty

string

null

yes

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

defaultValue

float

null

yes

The default value of the weight in case it is missing or invalid

write

boolean

true

yes

Specifies if the result should be written back as a node property

writeProperty

string

'sssp'

yes

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

nodeQuery

string

null

yes

The label to load from the graph. If null, load all nodes

relationshipQuery

string

null

yes

The relationship type to load from the graph. If null, load all nodes

direction

string

outgoing

yes

The relationship direction to load from the graph. If 'both', treats the relationships as undirected

Table 9.65. Results
Name Type Description

nodeCount

int

The number of nodes considered

totalCost

float

The sum of all weights along the path

loadMillis

int

Milliseconds for loading data

evalMillis

int

Milliseconds for running the algorithm

writeMillis

int

Milliseconds for writing result data back

The following will run the algorithm and stream results: 

CALL algo.shortestPath.stream(startNode:Node, endNode:Node, weightProperty:String
    {nodeQuery:'labelName', relationshipQuery:'relationshipName', defaultValue:1.0, direction:'OUTGOING'})
 YIELD nodeId, cost

Table 9.66. Parameters
Name Type Default Optional Description

startNode

node

null

no

The start node

endNode

node

null

no

The end node

weightProperty

string

null

yes

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

nodeQuery

string

null

yes

The label to load from the graph. If null, load all nodes

relationshipQuery

string

null

yes

The relationship type to load from the graph. If null, load all nodes

defaultValue

float

null

yes

The default value of the weight in case it is missing or invalid

direction

string

outgoing

yes

The relationship direction to load from the graph. If 'both', treats the relationships as undirected

Table 9.67. Results
Name Type Description

nodeId

int

Node ID

cost

int

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

9.4.2.7. Graph type support

The shortest path algorithms support the following graph types:

  • ✓ directed, unweighted:

    • direction: 'OUTGOING' or INCOMING, weightProperty: null
  • ✓ directed, weighted

    • direction: 'OUTGOING' or INCOMING, weightProperty: 'cost'
  • ✓ undirected, unweighted

    • direction: 'BOTH', weightProperty: null
  • ✓ undirected, weighted

    • direction: 'BOTH', weightProperty: 'cost'

9.4.2.8. Implementations

algo.shortestPath

  • Specify start and end node, find the shortest path between them.
  • Dijkstra single source shortest path algorithm.
  • There may be more then one shortest path, algorithm returns only one.
  • If initialized with an non-existing weight-property, it will treat the graph as unweighted.

algo.shortestPaths

  • Specify start node, find the shortest paths to all other nodes.
  • Dijkstra single source shortest path algorithm.
  • If initialized with an non-existing weight-property, it will treat the graph as unweighted.