DEV Community

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

Posted on • Edited on

Finding shortest social connection path

#algorithms #bfs #python

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.

Top comments (0)