Вернуть все возможные пути, построив словарь-предшественник в Python

Question

Если у меня есть словарь предшественника для одного сгенерированного графа, например:

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

Как я мог:

1) найти все возможные пути от точки А до Е и распечатать их?

Спасибо!

Код вставлен ниже:

уточнение кода:

G - это кортеж кортежей, внутренние кортежи - это пары вершин, которые связаны между собой одним способом: ((начало, конец) (начало, конец))

s - начальный узел

e является конечным узлом

def dfs_stack(G,s,e):
    stack = [s] 
    vertices = set([j for t in G for j in t]) 
    visited = dict([(v, False) for v in vertices])
    predecessor = dict([(v, []) for v in vertices])
    while stack:
        u = stack.pop()
        if visited[u] == False:
            visited[u] = True
            for w in get_neighbors(u, G): 
                if visited[w] == False:
                    predecessor[w].append(u)
                    stack.append(w)
                elif (visited[w] == True and w != e):
                    return 'CYCLICAL GRAPH'
    return predecessor_to_path(predecessor,s, e)

def predecessor_to_path(pdict, s, end, l=[]):
    l.append(end)
    if end == s:
        return l
    else:
        for p in pdict[end]:
           return predecessor_to_path(pdict, s, p, l)

В настоящее время это возвращает только кратчайший путь. Любые идеи о том, как предикатор_to_path может быть изменен, чтобы вернуть ВСЕ пути?

Answer 1

Все это делается с помощью классических алгоритмов графа, таких как поиск в глубину.

Вот отправная точка:

http://en.wikipedia.org/wiki/Spanning_tree#Algorithms