python - 考虑最大距离为图形寻找不同的路线

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))