A solution to the Interview Cake "MeshMessaging" problem (https://www.interviewcake.com/question/python/mesh-message)

network.json

{
    "Min"     : ["William", "Jayden", "Omar"],
    "William" : ["Min", "Noam"],
    "Jayden"  : ["Min", "Amelia", "Ren", "Noam"],
    "Ren"     : ["Jayden", "Omar"],
    "Amelia"  : ["Jayden", "Adam", "Miguel"],
    "Adam"    : ["Amelia", "Miguel"],
    "Miguel"  : ["Amelia", "Adam"],
    "Noam"    : ["Jayden", "William"],
    "Omar"    : ["Ren", "Min"]
}

shortest.py

#!/usr/bin/env python

# Interview cake MeshMessage (shortest path) problem.
# See https://www.interviewcake.com/question/python/mesh-message

# This solution implements both a depth-first and breadth-first solution.
# The breadth-first solution is the shortest path. 

# $ ./shortest.py network.json Min Adam
# depth-first: ['Min', u'William', u'Noam', u'Jayden', u'Amelia', 'Adam']
# breadth-first: ['Min', u'Jayden', u'Amelia', 'Adam']


import sys
import json
from collections import deque


def usage(fd=sys.stdout):
    fd.write("usage: ./shortest.py network.json <origin> <destination>\n")


def fatal_usage():
    usage(sys.stderr)
    sys.exit(1)


def parse_args():
    if len(sys.argv) < 4:
        fatal_usage()
    fname = sys.argv[1]
    with open(fname) as fd:
        network = json.load(fd)
    origin = sys.argv[2]
    dest = sys.argv[3]
    return (network, origin, dest)


# recursive, depth-first path finding algorithm.  note: does not find the shortest path.
def find_path_depth_first(network, origin, destination):
    if origin == destination:
        return [origin]
    else:
        return _find_path_depth_first_recur(network, origin, network[origin], destination, set([origin]))


def _find_path_depth_first_recur(network, current_node, neighbors, destination, visited):
    # print "shortest_recur", current_node, neighbors
    for n in neighbors:
        if n == destination:
            return [current_node, destination]
        elif n not in visited:
            visited2 = set(visited)
            visited2.add(n)
            path = _find_path_depth_first_recur(network, n, network[n], destination, visited2)
            if path is not None:
                return [current_node] + path
    return None


# breadth-first shortest path algorithm.
def shortest_path(network, origin, destination):
    queue = deque()
    if origin == destination:
        return [origin]
    else:
        path = [origin]
        seen = set(path)
        queue.append((path, seen))
        while len(queue) > 0:
            (path, seen) = queue.popleft()
            current = path[-1]
            for neighbor in network[current]:
                if neighbor in seen:
                    continue
                elif neighbor == destination:
                    return path + [destination]
                else:
                    path2 = path + [neighbor]
                    seen2 = set(seen)
                    seen2.add(neighbor)
                    queue.append((path2, seen2))
    return None


def test():
    network = json.loads("""
{
    "Min"     : ["William", "Jayden", "Omar"],
    "William" : ["Min", "Noam"],
    "Jayden"  : ["Min", "Amelia", "Ren", "Noam"],
    "Ren"     : ["Jayden", "Omar"],
    "Amelia"  : ["Jayden", "Adam", "Miguel"],
    "Adam"    : ["Amelia", "Miguel"],
    "Miguel"  : ["Amelia", "Adam"],
    "Noam"    : ["Jayden", "William"],
    "Omar"    : ["Ren", "Min"]
}
""")
    assert shortest_path(network, 'Min', 'Adam') == ['Min', 'Jayden', 'Amelia', 'Adam']
    # thanks to peter for these test cases
    assert shortest_path(network, 'Jayden', 'Adam') == ['Jayden', 'Amelia', 'Adam']
    assert shortest_path(network, 'Jayden', 'No One') is None
    assert shortest_path(network, 'Jayden', 'Jayden') == ['Jayden']
    assert shortest_path(network, 'Adam', 'William') == ['Adam', 'Amelia', 'Jayden', 'Min', 'William']
    assert shortest_path(network, 'Miguel', 'Jayden') == ['Miguel', 'Amelia', 'Jayden']


if __name__ == "__main__":
    if len(sys.argv) == 1:
        test()
    else:
        network, origin, dest = parse_args()
        print "depth-first:", find_path_depth_first(network, origin, dest)
        print "breadth-first (shortest path):", shortest_path(network, origin, dest)