def dfs4(p, d, G, V, P):
    s = p[-1]
    if noChildren(s, G):
        if s == d: P.append(p)
        return
    for n in children(s, G):
        if n in V: continue
        V.append(n)
        if n == d:
            P.append(p + n)
            V.pop( )
            continue
        dfs4(p + n, d, G, V, P)

def noChildren(s, G):
    return not s in G

def children(s, G):
    return G[s]

def findPaths(s, d, G):
    P = []
    V = [s]
    dfs4(s, d, G, V, P)
    print 'Graph: ' + str(G)
    print 'Paths found: ' + str(P)

def step(msg):
    raw_input(msg)

G = {'A':['B', 'E'], 'B':['C', 'D'], 'C':['A', 'F'], 'D':['E'], 'F':['E']}

findPaths('A', 'E', G)

G2 = {'A':['B', 'E'], 'B':['A', 'D', 'C'], 'D':['B', 'E'], 'C':['A', 'E'], 'E':['E']}

findPaths('A', 'E', G2)

findPaths('D', 'A', G2)

findPaths('E', 'A', G2)