GraphAcademy

Path Finding with GDS

Why Graphs?

Finding Shortest Paths using Cypher

Using the Graph Data Science library

Challenge: Dijkstra’s Source-Target Shortest Path

In the previous module, you learned that there are 206 shortest unweighted paths from Nashville to Phuket.

In this challenge, you will use the Dijkstra shortest path algorithm to recommend the shortest weighted path between the two airports based on the flight distance.

This challenge has two parts:

  1. Create a Projected Graph

  2. Find the Source-Target Shortest Path

Create a Projected Graph

In the integrated sandbox widow to the right, execute the following query to create a new graph projection. Note that when you start this challenge, any existing graph project named routes has been removed.

cypher
Create a Projected Graph
CALL gds.graph.project(
  'routes',
  'Airport',
  'HAS_ROUTE',
  {relationshipProperties:'distance'}
);

This query creates a new projected graph called routes, loading in all (:Airport) nodes and [:HAS_ROUTE] relationships. Each relationship will have a .distance property which will we use in the next step for calculating the shortest weighted path.

Find the Source-Target Shortest Path

Now that the graph has been projected into memory, run the gds.shortestPath.dijkstra.stream() procedure to calculate the shortest weighted path from Nashville (BNA) to Phuket (HKT).

cypher
Run the algorithm
MATCH (source:Airport {iata: "BNA"}),
      (target:Airport {iata:"HKT"})

CALL gds.shortestPath.dijkstra.stream(
  'routes',
  {
    sourceNode:source,
    targetNode:target,
    relationshipWeightProperty:'distance'
  }
) YIELD totalCost
RETURN totalCost;

What is the total cost?

The output of the second query should a number representing the total distance of the shortest weighted path from Nashville (BNA) to Phuket (HKT).

Enter the total cost below below and click the Check Answer button below to continue. Note: Make sure you enter the complete number including the decimal point.

  • ✓ 9387.0

Hint

When you run the Dijkstra algorithm, it will return multiple pieces of information. To filter that down to just totalCost you can use the YIELD clause like so:

MATCH (source:Airport {iata: 'BNA'}), (target:Airport {iata: 'HKT'})
CALL gds.shortestPath.dijkstra.stream(
.....
) YIELD totalCost;

Solution

You can run the following Cypher statement to find the total cost of the shortest weighted path between Nashville and Phuket.

The statement returns a single value from the procedure call, totalCost, which can be copied and pasted into the form field above.

// tag::project[]
CALL gds.graph.project(
  'routes',
  'Airport',
  'HAS_ROUTE',
  {relationshipProperties:'distance'}
);
// end::project[]

// tag::run[]
MATCH (source:Airport {iata: "BNA"}),
      (target:Airport {iata:"HKT"})

CALL gds.shortestPath.dijkstra.stream(
  'routes',
  {
    sourceNode:source,
    targetNode:target,
    relationshipWeightProperty:'distance'
  }
) YIELD totalCost
RETURN totalCost;
// end::run[]

Lesson Summary

In this Challenge you practiced how to calculate the shortest weighted path using the Dijkstra shortest path algorithm.

In the next challenge, you will use Yen’s algorithm to identify alternative shortest weighted path between two nodes.