考虑最大距离，查找图表的不同路线

Question

所以这是我的问题：

我正在尝试找到从C到C的所有不同路径，其中最大距离为30。

我认为我的停止条件存在问题，但我已经尝试了这么久以至于我看不出有什么问题（打印2但应该是7）。

Java中有一个针对我的问题的实现，但我想用Python（问题10）来实现：link

我的代码：

            from collections import defaultdict, deque


        class Graph(object):
            def __init__(self):
                self.nodes = set()
                self.edges = defaultdict(list)
                self.distances = {}

            def add_node(self, value):
                self.nodes.add(value)

            def add_edge(self, from_node, to_node, distance):
                self.edges[from_node].append(to_node)
                self.distances[(from_node, to_node)] = distance

        def are_these_nodes_adjacents(from_node, to_node):
            return to_node in graph.edges[from_node]

        def count_distance(graph, u, v, k, max_distance):
            if(k > 0 and u == v and k != max_distance): 
                return 1
            if(k > 0 and are_these_nodes_adjacents(u, v)): 
                return 1
            if(k <= 0): 
                return 0

            count = 0

            for i in ['A', 'B', 'C', 'D', 'E']:
                if(are_these_nodes_adjacents(u, i)):
                        count += count_distance(graph, i, v, k-graph.distances[(u, i)], max_distance)
            return count

        if __name__ == '__main__':
            graph = Graph()

            for node in ['A', 'B', 'C', 'D', 'E']:
                graph.add_node(node)

            graph.add_edge('A', 'B', 5)
            graph.add_edge('B', 'C', 4)
            graph.add_edge('C', 'D', 8)
            graph.add_edge('D', 'C', 8)
            graph.add_edge('D', 'E', 6)
            graph.add_edge('A', 'D', 5)
            graph.add_edge('C', 'E', 2)
            graph.add_edge('E', 'B', 3)
            graph.add_edge('A', 'E', 7)

            u = 'C'
            v = 'C'
            k = 30
            print(count_distance(graph, u, v, k, k))

Answer 1

代码中的以下条件：

if(k > 0 and u == v and k != max_distance):  
         return 1

只要再次返回节点C，就会返回并停止搜索。而不是这样做，您需要添加1来计数，并继续搜索。

你应该删除以下条件：

if(k > 0 and are_these_nodes_adjacents(u, v)): 
                return 1

你为什么拥有它？

这是生成的代码，根据需要打印7：

from collections import defaultdict


class Graph(object):
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}

    def add_node(self, value):
        self.nodes.add(value)

    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.distances[(from_node, to_node)] = distance

def are_these_nodes_adjacents(from_node, to_node):
    return to_node in graph.edges[from_node]

def count_distance(graph, u, v, k, max_distance):
    if(k <= 0): 
        return 0

    count = 0

    if(k > 0 and u == v and k != max_distance): 
        count += 1

    for i in ['A', 'B', 'C', 'D', 'E']:
        if(are_these_nodes_adjacents(u, i)):
                count += count_distance(graph, i, v, k-graph.distances[(u, i)], max_distance)
    return count

if __name__ == '__main__':
    graph = Graph()

    for node in ['A', 'B', 'C', 'D', 'E']:
        graph.add_node(node)

    graph.add_edge('A', 'B', 5)
    graph.add_edge('B', 'C', 4)
    graph.add_edge('C', 'D', 8)
    graph.add_edge('D', 'C', 8)
    graph.add_edge('D', 'E', 6)
    graph.add_edge('A', 'D', 5)
    graph.add_edge('C', 'E', 2)
    graph.add_edge('E', 'B', 3)
    graph.add_edge('A', 'E', 7)

    u = 'C'
    v = 'C'
    k = 30
    print(count_distance(graph, u, v, k, k))