Part 17: Calculating the Shortest Path Between Two Airports Using Dijkstra's Algorithm

Calculating the Shortest Path Between Two Airports Using Dijkstra's Algorithm

In this blog post, we'll explore how to Dijkstra's algorithm to calculate the shortest path between two airports in a weighted graph. Dijkstra's algorithm is popular algorithm for finding the shortest paths between nodes in a graph, particularly when the graph has weighted edges.

Step 1: Creating a Weighted Graph Projection

Before we can use Dijkstra's algorithm, we need to create a weighted graph projection. This projection will include nodes labeled Airport and relationships labeled HAS_ROUTE, with each relationship having a distance property representing the weight.

Query to Create a Weighted Graph Projection

CALL gds.graph.project(
    'routes-weighted',
    'Airport',
    'HAS_ROUTE',
    {
        relationshipProperties: 'distance'
    }
) YIELD
    graphName, nodeProjection, nodeCount, relationshipProjection, relationshipCount;

Breaking Down the Query

1. Graph Projection:

CALL gds.graph.project(
    'routes-weighted',
    'Airport',
    'HAS_ROUTE',
    {
        relationshipProperties: 'distance'
    }
)
YIELD
    graphName, nodeProjection, nodeCount, relationshipProjection, relationshipCount;

• 'routes-weighted': The name of the projected graph.

• 'Airport': The label of the nodes to include in the graph.

• 'HAS_ROUTE': The type of relationships to include in the graph.

• relationshipProperties: 'distance': Specifies that the distance property on relationships should be used as the weight.

• YIELD: Returns information about the projected graph, including its name, node projection, node count, relationship projection, and relationship count.

This query sets up a weighted graph named 'routes-weighted' that includes airports and routes with distances as weights.

Step 2: Calculating the Shortest Path with Dijkstra's Algorithm

Now that we have our weighted graph projection, we can use Dijkstra's algorithm to find the shortest path between two specific airports. In this example, we'll find the shortest path between Denver (DEN) and Mitchel (MLE).

Query to Calculate the Shortest Path

MATCH (source:Airport {iata: 'DEN'}), (target:Airport {iata: 'MLE'})
CALL gds.shortestPath.dijkstra.stream('routes-weighted', {
    sourceNode: source,
    targetNode: target,
    relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).iata AS sourceNodeName,
    gds.util.asNode(targetNode).iata AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).iata] AS nodeNames,
    costs,
    nodes(path) AS path
ORDER BY index;

Breaking Down the Query

1. Matching Source and Target Nodes:

MATCH (source:Airport {iata: 'DEN'}), (target:Airport {iata: 'MLE'})

• Finds the nodes representing Denver (DEN) and Mitchel (MLE).

2. Calling Dijkstra's Algorithm:

CALL gds.shortestPath.dijkstra.stream('routes-weighted', {
    sourceNode: source,
    targetNode: target,
    relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path;

• 'routes-weighted': The name of the projected graph.

• sourceNode: The starting node (Denver).

• targetNode: The ending node (Mitchel).

• relationshipWeightProperty: 'distance': Uses the distance property on relationships as the weight.

• YIELD: Returns information about each path, including the index, source and target nodes, total cost, node IDs, costs, and the path itself.

3. Returning the Desired Information:

RETURN
    index,
    gds.util.asNode(sourceNode).iata AS sourceNodeName,
    gds.util.asNode(targetNode).iata AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).iata] AS nodeNames,
    costs,
    nodes(path) AS path
ORDER BY index;

• index: The index of the path.

• sourceNodeName: The IATA code of the source node (Denver).

• targetNodeName: The IATA code of the target node (Mitchel).

• total: The total cost (distance) of the path.

  • nodeNames: A list of IATA codes for the nodes along the path.

  • costs: The individual costs of each segment of the path.

  • path: The path itself, represented as a list of nodes - ORDER BY index: Orders the results by the index of each path.

Query Explanation

This query finds the shortest path between Denver and Mitchel using Dijkstra's algorithm. By considering the distance property on relationships, we can determine the most efficient route between these two airports. The results will show the total cost, the nodes along the path, and the individual costs of each segment.

Conclusion

Using Dijkstra's algorithm in Neo4j allows us to calculate the shortest path between two nodes in a weighted graph efficiently. By following the steps outlined above, you can easily project a weighted graph and find the shortest path between any two nodes in your dataset. This capability is invaluable for applications such as route optimization, network analysis, and logistics planning.