backtracking на графике

Question

В python У меня есть график как представление списка смежности. и расстояние от конкретных точек до всех остальных элементов графика.

graph = { 
    1 :[2, 7], 
    2 :[1, 3], 
    3 :[2, 4, 8], 
    4 :[3, 5, 9], 
    5 :[4, 6, 9], 
    6 :[5, 8, 10], 
    7 :[1, 8,10], 
    8 :[3, 6, 7, 9], 
    9 :[4, 5, 8], 
    10:[7, 6] 
    } 

distance = {1: 1, 2: 0, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2, 10: 3} 

Как я могу отступиться путь от элемента: к примеру, если я буду пытаться вернуться назад с 10, он должен вернуть:

[10, 7, 1, 2] 
[10, 7, 8, 3] 
[10, 6, 8, 3] 

Я пытался сделать это рекурсивно

def findprev(graph, distance, el, path = []): 
    value = distance[el] 
    if value == 0: 
     print path 
     path = [] 

    for i in graph[el]: 
     if value - 1 == distance[i]: 
      path.append(i) 
      path = findprev(graph, distance, i, path) 
    return path 

, но, по-видимому, я теряю что-то важное, потому что результат:

[7, 1, 2] 
[8, 3] 
[6, 8, 3] 

Может кто-нибудь поможет найти ошибку

Answer 1

def findprev(graph, distance, el, path=None): 
    if path is None: 
     path = [el] 
    else: 
     path.append(el) 
    value = distance[el] 
    if value == 0: 
     print(path) 

    for i in graph[el]: 
     if value - 1 == distance[i]: 
      findprev(graph, distance, i, path[:]) 

findprev(graph, distance, 10) 

Выход:

[10, 7, 1, 2] 
[10, 7, 8, 3] 
[10, 6, 8, 3] 

Или, если вы хотите возвратить полученные пути:

def findprev(graph, distance, el, path=None): 
    if path is None: 
     path = [el] 
    else: 
     path.append(el) 
    value = distance[el] 
    if value == 0: 
     return [path] 

    result = [] 
    for i in graph[el]: 
     if value - 1 == distance[i]: 
      paths = findprev(graph, distance, i, path[:]) 
      for p in paths: 
       result.append(p) 
    return result 

Answer 2

Вот другое решение твоя проблема. Я переименовал distance в distances, потому что это показалось мне лучшим именем, и я использую имя distance для расстояния каждой отдельной точки.

>>> def find_paths(point,path=[]): 
     distance = distances[point] 
     elements = graph[point] 
     if distance == 0: 
      yield path + [point] 
     else: 
      for element in elements: 
       if distances[element] == distance - 1: 
        for item in find_paths(element,path+[point]): 
         yield item 


>>> for path in find_paths(10): 
     print path 


[10, 7, 1, 2] 
[10, 7, 8, 3] 
[10, 6, 8, 3]