This section describes the Shortest Path algorithm in the Neo4j 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.
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.
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.
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 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.getNodeById(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
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:
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
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 |
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
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 |
Name | Type | Description |
---|---|---|
nodeId |
int |
Node ID |
cost |
int |
The cost it takes to get from start node to specific node |
The shortest path algorithms support the following graph types:
✓ directed, unweighted:
✓ directed, weighted
✓ undirected, unweighted
✓ undirected, weighted
If 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.
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
algo.shortestPath
algo.shortestPaths