DEV Community

Cover image for Finding shortest social connection path
Santhosh Balasa
Santhosh Balasa

Posted on • Updated on

Finding shortest social connection path

Human connections are like networks, I know someone, and they know someone else and so on, It could be friendship, relationship etc.

Let's assume that I need to find the shortest social connection path from me to Queen of England (Well maybe :p).

We represent this in a graph format:

{
 'ali': ['mo'],
 'angela': ['queen', 'anna'],
 'anna': [],
 'dave': [],
 'dog': ['liea', 'dave'],
 'jimbo': [],
 'lee': [],
 'liea': ['lee'],
 'me': ['mum', 'dog', 'teacher'],
 'mo': [],
 'mum': ['angela', 'liea'],
 'queen': [],
 'teacher': ['ali', 'jimbo']
}
Enter fullscreen mode Exit fullscreen mode

Now lets find the shortest social connection path:

def find_path(start, end, graph, path=[]):
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(node, end, graph, path)
            if newpath:
                return newpath
    return None
Enter fullscreen mode Exit fullscreen mode

Output:

>>> find_path("me", "queen", graph)
['me', 'mum', 'angela', 'queen']
Enter fullscreen mode Exit fullscreen mode

This solution is loosely based on breadth-first search graph algorithm to find the shortest path.

Discussion (0)