GraphAcademy

Introduction to Graph Databases Workshop

Graph Databases

Cypher

Finding the Shortest Path

Shortest Path

In Neo4j, you can find the shortest path between two nodes using the SHORTEST [k] clause.

This is useful for queries involving relationships like connections, friendships, or travel routes.

This query finds the shortest connection path between Tom Hanks and Meg Ryan, regardless of the relationship types:

cypher
MATCH (a:Person {name: "Tom Hanks"}), (b:Person {name: "Meg Ryan"})
MATCH p = SHORTEST 1 (a)-[*]-(b)
RETURN p

SHORTEST 1 indicates that you want the first shortest path found.

Limiting path length

To avoid expensive computations or infinite loops, you can limit the length of the path:

cypher
Shortest path with a max length of 4
MATCH (a:Person {name: "Tom Hanks"}), (b:Person {name: "Meg Ryan"})
MATCH p = SHORTEST 5 (a)-[*..4]-(b)
RETURN p

Using [*..4] limits the traversal to a maximum of 4 relationships.

You can use directed or undirected relationships in shortest path searches.

(a)-[*]-(b) is undirected

(a)-[*]→(b) is directed

Specific relationship types

By specifying a relationship type, you can find the shortest related path.

cypher
MATCH (a:Person {name: "Tom Hanks"}), (b:Person {name: "Meg Ryan"})
MATCH p = SHORTEST 5 (a)-[:ACTED_IN*..4]-(b)
RETURN p

Specific path length

You can specify the exact length of the path.

This query will find indirect relationships between Tom Hanks and Meg Ryan, with exactly 4 hops:

cypher
MATCH (a:Person {name: "Tom Hanks"}), (b:Person {name: "Meg Ryan"})
MATCH p = SHORTEST 1 (a)-[*4]-(b)
RETURN p

Challenges

Complete the queries to anwser the following questions:

  1. What is the lowest rated movie.

    cypher
    MATCH (m:Movie)<-[r:RATED]-(:User)
RETURN m.title, ???(r.rating) as ??????
ORDER BY ??????
LIMIT 1

  2. Whats the shortest path between the lowest rated movie and Tom Hanks.

    cypher
    MATCH (m:Movie {title: "??????"})
MATCH (t:Person {name: "Tom Hanks"})
MATCH p = ?????? ? (?)-[:ACTED_IN*]-(?)
RETURN ?

  3. Use WITH to combine these two queries into one.

Click to reveal the answers

  1. Find the lowest rated movie.

    cypher
    MATCH (m:Movie)<-[r:RATED]-(:User)
RETURN m.title, avg(r.rating) as avgRating
ORDER BY avgRating
LIMIT 1

  2. Find the shortest path between actors in the lowest rated movie and Tom Hanks.

    cypher
    MATCH (m:Movie {title: "Conspirator, The"})
MATCH (t:Person {name: "Tom Hanks"})
MATCH p = SHORTEST 1 (m)-[:ACTED_IN*]-(t)
RETURN p

  3. Use WITH to combine these two queries into one.

    cypher
    MATCH (m:Movie)<-[r:RATED]-(:User)
WITH m, avg(r.rating) as avgRating
ORDER BY avgRating LIMIT 1

MATCH (t:Person {name: "Tom Hanks"})
MATCH p = SHORTEST 1 (m)-[:ACTED_IN*]-(t)
RETURN p

Summary

In this lesson, you learned how to find the shortest path between two nodes using Cypher’s shortestPath() function. You also practiced limiting path lengths, using directed paths, and measuring the number of relationships in a path.