Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
June 25, 2021 03:53 pm GMT

Finding shortest social connection path

Human connections are like networks, I know someone, and they know someone else etc, 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.

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']}

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 path    return None

Output:

>>> find_path("me", "queen", graph)['me', 'mum', 'angela', 'queen']

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


Original Link: https://dev.to/sbalasa/finding-path-in-graph-4kp8

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To