python - 为什么这个图形路由会重复

Question

我一直在学习 Python 中的图形算法，并且想知道为什么我在结果中得到了重复的路径。

这是我的代码

from collections import defaultdict

our_graph = defaultdict(list)


def run_graph():
    print('Creating Graph...')
    add_edges("London", "Barcelona")
    add_edges("Barcelona", "Madrid")
    add_edges("Madrid", "Ottawa")
    add_edges("Madrid", "Berlin")
    add_edges("London", "Ottawa")

    print('\nOur Graph:')
    print(our_graph)

    print('\nEdges:')
    print(list_edges())

    print('\nTesting Paths To Invalid Nodes:')
    print(find_all_paths("LDN", "Ottawa"))
    print(find_all_paths("London", "X"))

    print('\nTesting Paths To Valid Nodes:')
    print(find_all_paths("London", "Ottawa"))
    print('---')
    print(find_all_paths("London", "Berlin"))


def add_edges(a, b):
    our_graph[a].append(b)
    our_graph[b].append(a)


def list_edges():
    edges = []
    for node in our_graph:
        for next_node in our_graph[node]:
            edges.append((node, next_node))
    return edges


def find_all_paths(start, end, path=[]):
    # If there isn't a node with that name
    if our_graph[start] == [] or our_graph[end] == []:
        return 'Can\'t find nodes ' + start + " " + end
    else:
        # create a path
        path = path + [start]
        # If start node is the end
        if start == end:
            return [path]
        paths = []
        newpaths = []
        # For each node
        for node in our_graph[start]:
            # If node not already in saved path
            if node not in path:
                # Search the paths of that new node
                newpaths = find_all_paths(node, end, path)
            # Append new path to paths
            for newpath in newpaths:
                paths.append(newpath)
        return paths


if __name__ == '__main__':
    run_graph()

我从 print(find_all_paths("London", "Berlin")) 得到的结果

是

[['London', 'Barcelona', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin']]

如您所见，伦敦-渥太华-马德里-柏林的路线重复了。你能解释一下为什么吗？

Answer 1

问题出在这里:

if node not in path:
    # Search the paths of that new node
    newpaths = find_all_paths(node, end, path)
# Append new path to paths
for newpath in newpaths:
    paths.append(newpath)

如果 node 已经在 path 中，将使用旧的 newpaths。您只需要将 for 循环移动到 if 语句下即可:

if node not in path:
    # Search the paths of that new node
    newpaths = find_all_paths(node, end, path)
    # Append new path to paths
    for newpath in newpaths:
        paths.append(newpath)

或:

if node not in path:
    # Search the paths of that new node
    paths += find_all_paths(node, end, path)

此外，我建议使用 defaultdict(set) 而不是列表。