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']
}
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
Output:
>>> find_path("me", "queen", graph)
['me', 'mum', 'angela', 'queen']
This solution is loosely based on breadth-first search graph algorithm to find the shortest path.
Top comments (0)