Weighted Shortest Paths

Projecting Weighted Graphs in GDS

To use the weighted shortest path algorithms built into the Neo4j Graph Data Science library, you will first need to create a graph projection in memory using the gds.graph.project() procedure. This topic is covered in more detail in the Neo4j Graph Data Science Fundamentals course.

When dealing with a single relationship type or having identical weights on all relationship types, you can use the relationshipProperties configuration parameter. relationshipProperties has three possible inputs:

In our dataset, we only have one property to represent weight, .distance, and it is present for all relationships so we don’t need to provide a default value. So in this case we can use a single string.

You can run the following Cypher statement to project the airport routes graph along with the distance relationship weight:

CALL gds.graph.project(
  'routes',                            // (1)
  'Airport',                           // (2)
  'HAS_ROUTE',                         // (3)
  {relationshipProperties:'distance'}  // (4)
);

Common Weighted Shortest Path Algorithms

In this lesson, we will cover two of the most commonly used algorithms that come with the Neo4j Graph Data Science library.

MATCH (source:Airport {iata: "CDG"}),  // (1)
      (target:Airport {iata:"LIS"})

CALL gds.shortestPath.dijkstra.stream(
  'routes',  // (2)
  {
    sourceNode: source,  // (3)
    targetNode: target,  // (4)
    relationshipWeightProperty: 'distance' // (5)
  }
)
YIELD nodeIds, costs, totalCost // (6)
RETURN [nodeId in nodeIds | gds.util.asNode(nodeId).descr] AS airports, costs, totalCost

Yen’s Algorithm

Yen’s k-Shortest Path algorithm, also referred to as Yen’s Shortest Path algorithm is similar to Dijkstra’s shortest path algorithm with the exception of a configurable k value, where k represents the number of shortest paths to return.

The algorithm makes sure that an already discovered shortest path will not be traversed again.

An implementation Yen’s algorithm is stored under the gds.shortestPath.yens namespace in the Neo4j Graph Data Science library. The gds.shortestPath.yens.stream() procedure can be called to calculate the k shortest weighted path between nodes.

You can run the following Cypher statement to calculate the three shortest weighted path between Paris Charles de Gaulle and Lisbon Portela Airport airports using the Yen’s algorithm.

MATCH (source:Airport {iata: "CDG"}),
      (target:Airport {iata:"LIS"})

CALL gds.shortestPath.yens.stream(
  'routes',
  {
    sourceNode:source,
    targetNode:target,
    relationshipWeightProperty:'distance',
    k:3 // (1)
  })
YIELD index, nodeIds, totalCost // (2)
RETURN index, [nodeId in nodeIds | gds.util.asNode(nodeId).descr] AS airports, totalCost

From the results, you can see that the shortest path is identical to the value returned by Dijkstra’s algorithm above, but two additional routes are suggested.

If you were to fly from Paris to Lisbon via Nantes, you would make additional 9 miles or additional 10 miles via Bilbao.

Check your understanding