Challenge: Source-Target Shortest Path

Now for another challenge.

There may be many circumstances where the shortest weighted path may not be the most optimal, the departure time may be unsuitable or services on the flight may not be adequate.

In this case, it would make sense to find multiple options to give the end-user choice.

As mentioned, you want to display alternative routes to your users in your application. Use the Yen’s algorithm to identify the three shortest paths from Nashville (BNA) to Phuket (HKT).

What is the total cost of traversing the third shortest path from Nashville to Phuket?

Third Shortest Path

What is the total cost of traversing the third shortest path from Nashville to Phuket?

Modify the query to find the three shortest weighted paths and enter the totalCost value into the form field below. Note: Make sure you enter the complete number including the decimal point.

  • ✓ 9389.0

Once you have entered the answer, click the Check Answer button below to continue.

Hint

The solution is very similar to the Dijkstra example.

You can use the same configuration as before, and only add the k parameter. Make sure you copy the totalCost value of the third row as that is what the question is asking for.

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

Solution

You can run the following Cypher statement to identify the three shortest paths from Nashville to Phuket.

MATCH (source:Airport {iata: "BNA"}),
      (target:Airport {iata:"HKT"})

CALL gds.shortestPath.yens.stream(
  'routes',
  {
    sourceNode:source,
    targetNode:target,
    relationshipWeightProperty:'distance',
    k:3
  }
) YIELD index, totalCost
WHERE index = 2 // index starts at 0
RETURN totalCost

The statement uses a WHERE clause to only return the result where the index value is 2 (representing the third row from a zero-based index).

Lesson Summary

In this challenge you practiced using Yen’s algorithm to identify the three shortest paths between two airports.

This completes the lessons and challenges for this course.