Finding verschiedene Routen für einen Graphen mein Problem, es ist also hier eine maximale Entfernung

Question

Berücksichtigung

Ich versuche, alle verschiedene Wege von C nach C zu finden, wo die maximale Entfernung 30

ich denke, ist dass es ein Problem mit meinen Stopp-Bedingungen gibt, aber ich versuche es so lange, dass ich nicht sehen kann, was falsch ist (druckt 2, sollte aber 7 sein).

Es gibt eine Implementierung in Java für meine Probleme, aber ich wollte es in Python (Problem 10) tun: link

Mein Code:

  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

Die folgende Bedingung im Code:

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

Sie kehren zurück und stoppen die Suche, sobald Sie wieder zu Knoten C zurückkehren. Anstatt dies zu tun, müssen Sie 1 zum Zählen hinzufügen und die Suche fortsetzen.

Und Sie sollten die folgende Bedingung löschen:

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

Warum haben Sie es?

Dies ist der resultierende Code ist die 7 nach Bedarf druckt:

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