Shortest Path

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, path

df = 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 dist

df = 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, path

df = 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, n

PLAN_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 |
+-------+--------------+----------------+

Get Started

Concepts

Benchmarks

Query Language

Importing data

Graph Development

Vector Search

Graph Algorithms

Tutorials

Python SDK

Troubleshooting

Sample dataset

Syntax

Basic usage

Returning only the distance or only the path

Multiple sources or targets

Limitations

​Sample dataset

​Syntax

​Basic usage

​Returning only the distance or only the path

​Multiple sources or targets

​Limitations

Sample dataset

Syntax

Basic usage

Returning only the distance or only the path

Multiple sources or targets

Limitations