GraphAcademy

Path Finding with GDS

Why Graphs?

Finding Shortest Paths using Cypher

Using the Graph Data Science library

Challenge: Cypher shortest paths

Now for another challenge.

We are interested in finding the total number of shortest paths between BNA and HKT airports.

How many options do you have to get from Nashville to Phuket with the smallest amount of flights?

In the previous challenge you found the first path from Nashville (BNA) to Phuket (HKT) with the shortest number of flights.

Now you will examine if there are multiple routes from Nashville to Phuket with the same number of flights.

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

  1. Use the allShortestPaths function to find all the paths that have the shortest length.

  2. Count the number of paths returned with the count function.

Enter the number of routes in the box below:

  • ✓ 206

Hint

You are looking for the total number of path objects between BNA and HKT returned by the allShortestPaths() function.

You can find the result by counting the shortest paths between the two airports with the count() aggregation function.

Solution

The answer is 206

You can use the following query to count the number of shortest routes from Nashville (BNA) to Phuket (HKT):

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

Summary

In this challenge, you demonstrated your skills in finding all the shortest unweighted paths.

In the next module, you will learn about weighted paths, and how to use the Neo4j Graph Data Science library to identify the most optimal weighted routes between airports.