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 this tier of algorithm, see here.

This section includes:

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.

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

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 run the algorithm and write back results:

```
CALL gds.alpha.shortestPath.write(configuration: Map)
YIELD nodeCount, totalCost, createMillis, computeMillis, writeMillis
```

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 |

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 nodeId, cost
```

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

Name | Type | Description |
---|---|---|

nodeId |
Integer |
Node ID |

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

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);
```

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,
weightProperty: 'cost'
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).name AS name, cost
```

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,
weightProperty: 'cost',
writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost
```

nodeCount | totalCost |
---|---|

5 |
160 |

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,
weightProperty: 'weight',
writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost
```