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)