This content originally appeared on DEV Community and was authored by Santhosh Balasa
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.
This content originally appeared on DEV Community and was authored by Santhosh Balasa
Santhosh Balasa | Sciencx (2021-06-25T15:53:35+00:00) Finding shortest social connection path. Retrieved from https://www.scien.cx/2021/06/25/finding-shortest-social-connection-path/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.