graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'],
         'D': ['C'], 'E': ['C'], 'F': []}

def findPathCycle(graph, start, end):
    path = [start]
    if start == end:
        return path
    if not start in graph.keys():
        return None
    for node in graph[start]:
        newpath = findPathCycle(graph, node, end)
        if newpath:
            path.extend(newpath)
            return path
    return None

def findPath(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not start in graph.keys():
        return None
    for node in graph[start]:
        if node not in path:
            newpath = findPath(graph, node, end, path)
            if newpath: return newpath
    return None


def dfs(graph, start, searchFor):
    visited, stack = [], [start]
    while stack:
        vertex = stack.pop()
        if vertex == searchFor:
            return vertex
        if vertex not in visited:
            visited.append(vertex)
            stack.extend(graph[vertex])
    return None

def bfs(graph, start, searchFor):
    visited, stack = [], [start]
    while stack:
        vertex = stack.pop(0)
        if vertex == searchFor:
            return vertex
        if vertex not in visited:
            visited.append(vertex)
            stack.extend(graph[vertex])
    return None

def findAllPaths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not start in graph.keys():
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = findAllPaths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

def findShortestPath(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not start in graph.keys():
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = findShortestPath(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

#print(findPath(graph, 'A', 'C'))
#print(dfs(graph, 'A', 'C'))
#print(bfs(graph, 'A', 'E'))
print(findAllPaths(graph, 'A', 'C'))
print(findShortestPath(graph, 'A', 'C'))

