Shortest Path

TuringDB’s shortestPath statement 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)

​

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
0  11.29  [0, 1, 6]

path alternates node and edge IDs: node 0, edge 1, node 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
0  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
0  12.6  [1, 5, 6]

If a set matches several source and target nodes, only the single best pair is returned.

​

Usage notes

MATCH (n{name:"Ashchurch"}), (m{name:"Worcestershire Parkway"})
shortestPath(n, m, distance, dist, path)
RETURN dist, path, n

ANALYZE_ERROR: Cannot return n after SHORTESTPATH.

• Directed. Outgoing edges are followed. When the target cannot be reached from the source, the query returns zero rows.
• RETURN follows directly. Put ORDER BY and LIMIT on that RETURN.
• Reading path. path is a flat list of IDs. To get names and properties, map the IDs back with a second query (see below).
• Where the other nodes come from. A join can feed an endpoint: MATCH (x {name: "Bromsgrove"})-[:LINK]->(a), (b {name: "Worcester Shrub Hill"}) shortestPath(a, b, distance, dist, path) RETURN dist, path.

​

Naming the stations along the route

To turn the IDs in path back into names, run a second query. The even positions of path are nodes:

row = client.query("""
MATCH (a:Station {name: 'Bromsgrove'}), (b:Station {name: 'Worcester Shrub Hill'})
shortestPath(a, b, distance, dist, path)
RETURN dist, path
""").iloc[0]

node_ids = sorted({int(i) for i in row["path"][0::2]})
names = client.query(f"UNWIND {node_ids} AS x MATCH (n) WHERE n = x RETURN id(n) AS id, n.name AS name")

The UNWIND list is a literal of distinct IDs and x is not returned, so this is a constant scan (see lookup by node ID).

For large graphs prefer shortestPath over variable-length paths: variable-length matching enumerates every path.