GraphAcademy

Neo4j Graph Data Science Fundamentals

Graph Algorithms

Graph Machine Learning

Challenge: Find the Shortest Path

Now for a challenge.

Shortest Path

What is the shortest path between 'Kevin Bacon' and 'Peta Wilson'?

You can use the same projection and a similar query to the previous lesson to find the answer.

You will need to:

  1. Create a projection (or use the same one as the previous lesson) of Actor and Movie nodes and ACTED_IN and DIRECTED relationships.

  2. Create a query that matches the 2 Actor nodes and uses gds.shortestPath.dijkstra.stream function to find the shortest path

  3. Count how many relationships there are between the source and target nodes.

Enter the number of relationship hops between 'Kevin Bacon' and 'Peta Wilson':

  • ✓ 6

Hint

This is the Cypher you used in the previous lesson to find the shortest path between Kevin Bacon and Denzel Washington.

cypher
// Create projection
CALL gds.graph.project('proj',
    ['Person','Movie'],
    {
        ACTED_IN:{orientation:'UNDIRECTED'},
        DIRECTED:{orientation:'UNDIRECTED'}
    }
);

// Find shortest path
MATCH (kevin:Actor{name : 'Kevin Bacon'})
MATCH (denzel:Actor{name : 'Denzel Washington'})

CALL gds.shortestPath.dijkstra.stream(
    'proj',
    {
        sourceNode:kevin,
        TargetNode:denzel
    }
)

YIELD sourceNode, targetNode, path
RETURN sourceNode, targetNode, nodes(path) as path;

There is a path consisting of four relationships between Kevin Bacon and Denzel Washington.

Solution

You will need to create a graph projection, that includes the Person and Movie nodes and the ACTED_IN and DIRECTED relationships.

cypher
CALL gds.graph.project('proj',
    ['Person','Movie'],
    {
        ACTED_IN:{orientation:'UNDIRECTED'},
        DIRECTED:{orientation:'UNDIRECTED'}
    }
);

Then you can use a similar query to the one used in the previous lesson to find the shortest path between Kevin Bacon and Peta Wilson.

cypher
MATCH (kevin:Actor{name : 'Kevin Bacon'})
MATCH (peta:Actor{name : 'Peta Wilson'})

CALL gds.shortestPath.dijkstra.stream(
    'proj',
    {
        sourceNode:kevin,
        TargetNode:peta
    }
)

YIELD sourceNode, targetNode, path
RETURN sourceNode, targetNode, nodes(path) as path;

The answer is the number of relationships in the path. There are 6 relationships between Kevin Bacon and Peta Wilson.

Summary

In this lesson you applied the knowledge from the last lesson to find the shortest path between two actors using a graph projection.

In the next lesson, you will learn more about Community Detection Algorithms.