TuringDB’s shortestPath processor runs a Dijkstra search from a source set of nodes to a target set of nodes, returning the shortest distance and the path taken based on a numeric edge weight property.
Sample dataset
The examples on this page use a small railway network. Run the following query to create it:
CREATE (asch:Station {name:"Ashchurch"}),
(bmv:Station {name:"Bromsgrove"}),
(cnm:Station {name:"Cheltenham Spa"}),
(dtw:Station {name:"Droitwich Spa"}),
(hby:Station {name:"Hartlebury"}),
(psh:Station {name:"Pershore"}),
(wop:Station {name:"Worcestershire Parkway"}),
(wof:Station {name:"Worcester Foregate Street"}),
(wos:Station {name:"Worcester Shrub Hill"})
CREATE (asch)-[:LINK {distance: 7.25}]->(cnm),
(asch)-[:LINK {distance: 11.29}]->(wop),
(asch)-[:LINK {distance: 14.75}]->(wos),
(bmv)-[:LINK {distance: 31.14}]->(cnm),
(bmv)-[:LINK {distance: 6.16}]->(dtw),
(bmv)-[:LINK {distance: 12.6}]->(wop),
(dtw)-[:LINK {distance: 5.64}]->(hby),
(dtw)-[:LINK {distance: 6.03}]->(wof),
(dtw)-[:LINK {distance: 5.76}]->(wos),
(psh)-[:LINK {distance: 4.16}]->(wop),
(wop)-[:LINK {distance: 3.71}]->(wos),
(wof)-[:LINK {distance: 0.65}]->(wos)Syntax
shortestPath(sourceSet, targetSet, edgePropName, distanceReturnVar, pathReturnVar)| Parameter | Description |
|---|---|
sourceSet | Variable bound to the source node(s) via a preceding MATCH clause |
targetSet | Variable bound to the target node(s) via a preceding MATCH clause |
edgePropName | Name of the numeric edge property to use as weight |
distanceReturnVar | Output variable name for the total shortest distance |
pathReturnVar | Output variable name for the path string |
Basic usage
- Cypher
- Python SDK
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN dist, pathdf = client.query("""
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN dist, path
""")
print(df)+-------+--------------+
| dist | path |
+-------+--------------+
| 11.29 | (0)-[1]->(6) |
+-------+--------------+
Returning only the distance or only the path
Both output variables are always computed — you can choose to return one or both:
- Cypher
- Python SDK
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN distdf = client.query("""
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN dist
""")
print(df)+-------+
| dist |
+-------+
| 11.29 |
+-------+
Multiple sources or targets
You can pass multiple nodes to the source or target set — shortestPath will find the shortest distance across all combinations and return the best one:
- Cypher
- Python SDK
MATCH (n), (m{name:"Worcestershire Parkway"})
WHERE n.name = "Bromsgrove" OR n.name = "Cheltenham Spa"
shortestPath(n, m, distance, dist, path)
RETURN dist, pathdf = client.query("""
MATCH (n), (m{name:"Worcestershire Parkway"})
WHERE n.name = "Bromsgrove" OR n.name = "Cheltenham Spa"
shortestPath(n, m, distance, dist, path)
RETURN dist, path
""")
print(df)+------+--------------+
| dist | path |
+------+--------------+
| 12.6 | (1)-[5]->(6) |
+------+--------------+
Limitations
Any variable on a pattern going into a shortestPath processor cannot be returned in the RETURN clause — they are consumed by the processor. The following query will produce an error:
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN dist, path, nPLAN_ERROR: Unexpected exception: projection variable n not found in output column
You can still MATCH additional nodes outside of the source and target sets and include them in RETURN. The result will be a cartesian product with the shortest path output:
MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"}), (p{name:"Cheltenham Spa"})
shortestPath(n, m, distance, dist, path)
RETURN dist, path, p.name+-------+--------------+----------------+
| dist | path | p.name |
+-------+--------------+----------------+
| 11.29 | (0)-[1]->(6) | Cheltenham Spa |
+-------+--------------+----------------+