GraphAcademy

Path Finding with GDS

Why Graphs?

Finding Shortest Paths using Cypher

Using the Graph Data Science library

Challenge: Cypher shortest paths

In the previous lesson, you learned that the shortestPath() Cypher function will return the single shortest, unweighted path between two nodes.

The output of this function is a Path object, which you pass to the the length() function to find the length of the shortest path.

You will now use this knowledge to execute a Cypher query in the integrated Sandbox window to the right of the screen.

How many flights you have to take to get from BNA to HKT?

We are interested in finding the shortest path between Nashville (BNA) and Phuket (HKT) airports. You can filter nodes using the iata (airport code) property.

Replace the ??? in the query on the right of the screen to:

  1. Filter source and target nodes to BNA and HKT airports using the iata property.

  2. Update the shortestPath function to use a path between source and target nodes via the HAS_ROUTE relationship.

The length function returns the length of the path (number of relationships).

Enter the length of the shortest path between BNA and HKT airports:

  • ✓ 3

Hint

In the previous lesson, you reviewed this Cypher query that found the shortest path between the cities of Baltimore and Frankfurt:

cypher
MATCH (source:Airport {city:"Baltimore"}),
      (target:Airport {city:"Frankfurt"})
MATCH p = shortestPath((source)-[:HAS_ROUTE*1..10]->(target))
RETURN p

Solution

The answer is 3.

You can use the following query to find the shortest route between Nashville (BNA) to Phuket (HKT):

cypher
MATCH (source:Airport {iata: 'BNA'}), (target:Airport {iata: 'HKT'})  
MATCH p=shortestPath((source)-[:HAS_ROUTE*]->(target))
RETURN length(p) AS result

Summary

In this challenge, you demonstrated your skills in finding the shortest unweighted path between two nodes.

In the next challenge, you will use the allShortestPaths() function to identify multiple shortest paths between nodes.