파이썬에서 재귀를 통해 살아남는 목록에 문제가 있습니다. 그래프에서 가능한 모든 경로 찾기

저는 완전히 연결된 그래프 (다른 노드에서 그래프의 모든 노드로 이동할 수 있음)를 가져 와서 주어진 최대 거리보다 짧은 해당 그래프에서 가능한 모든 경로를 찾는 파이썬 프로그램을 작성하고 있습니다.

이것이 내가 지금까지 코딩 한 것입니다.

def find_all_routes (cur_node, graph, willing_to_travel, visited, routesdict):
    """ Finds all routes possible within a certain distance.
    inputs
        cur_node: a dictionary with n entries, each of which is the distance to the nth
            dictionary in graph.
        graph: a list of n dictionaries, each of which contains n entries, each of which
            is the distance to the nth item in the list.
        willing_to_travel: the maximum distance we are willing to travel.
        visited: initialized as an empty list, will be populated nodes we've been to.
        all_routes: initialized as an empty list.
    Affects:
        all_routes is populated with every route permutation that can be traveled in under willing_to_travel distance.
    """
    #Add our current location to the visited list.
    for i in cur_node:
        if cur_node[i] == 0:
            visited.append(graph[i])

    # Add the current route to the dictionary.
    entry_no = len(routesdict)
    routesdict[entry_no] = visited
    print ("routesdict", routesdict)            # Just for diagnostic purposes.

    # Recursion with other nodes we can reach as the new start node.
    for i in cur_node:                               # For every place in the dictionary
        if graph[i] not in visited:                  # if we have not been there
            if cur_node[i] <= willing_to_travel:     # And if we can afford to go there
                find_all_routes(graph[i], graph, willing_to_travel - cur_node[i], visited, routesdict)

    return routesdict

def main():

    graph = [
        {0: 0.00, 1: 0.12, 2: 0.10},
        {0: 0.12, 1: 0.00, 2: 0.22},
        {0: 0.10, 1: 0.22, 2: 0.00}]

    max_distance = 10.0
    been_to = []
    routesdict = dict()

    routes = find_all_routes (graph[0], graph, max_distance, been_to, routesdict)

print ("Final output: ", routes)

if __name__ == "__main__":
    main()

이 결과는 다음과 같습니다.

routesdict:    {0: [{0: 0.0, 1: 0.12, 2: 0.1}]}
routesdict:    {0: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}], 1: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}]}
routesdict:    {0: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1: 0.22, 2: 0.0}], 1: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1: 0.22, 2: 0.0}], 2: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1: 0.22 , 2: 0.0}]}
Final output:  {0: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1: 0.22, 2: 0.0}], 1: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1: 0.22, 2: 0.0}], 2: [{0: 0.0, 1: 0.12, 2: 0.1}, {0: 0.12, 1: 0.0, 2: 0.22}, {0: 0.1, 1:0.22, 2: 0.0}]}

도대체 추악하지만 우리가 방문하는 노드의 관점에서 다시 말하면 다음과 같이 진행됩니다.

routesdict [0]
routesdict [0, 1] [0, 1]
routesdict [0, 1, 2]  [0, 1, 2] [0, 1, 2]
Final out: [0, 1, 2]  [0, 1, 2] [0, 1, 2]

3 노드 그래프의 경우 가능한 모든 경로를 완료 할 수있을만큼 최대 거리가 충분히 높으면 출력이 다음과 같이 표시되기를 바랍니다.

All possible routes*: [0], [0,1], [0,1,2], [0,2], [0,2,1]
*If we must start at node 0.

===============

이제는 문제가 있다고 생각하지만 해결을 통해 생각할 수 없습니다. 문제는 "방문 된"목록의 현재 값을 뜯어 내고 계속 진행하는 대신 "방문한"목록의 정체성을 유지하고 있다는 것입니다.

따라서 재귀를 통해 처음으로 routedict [0]은 "visited"로 정의되고 노드 [0]이 첫 번째 경로로 올바르게 지정됩니다. 그러나 방문이 변경되면 routedict [0]이 업데이트되고 이제 [0,1]이라고 표시됩니다.

이것은 함수가 내가 원하는 재귀를 수행하는 것을 막는 것과 똑같은 일이며, 이것이 내가 기대하는 5 개 대신 3 개의 가능한 경로를 제공하는 이유입니다.

그래서, 더 깊은 재귀로 들어가면서 내 "방문한"목록을 유지하는 좋은 방법이 있지만 목록이 나머지 세계에 소급 적용되지 않도록 할 수 있습니까?

읽어 주셔서 감사합니다!

편집하다:

나는 이미 노선을 routedict로 변경하여 경로를 가져 오는 문제를 해결했습니다.

routesdict[entry_no] = visited[:]

그러나 방문 목록이 내 재귀를 깨지 않는 것에 대해 훨씬 더 단서가 없습니다!