Wie berechnet man das Gesamtgewicht der Pfade von gerichteten gewichteten Graphen in DFS in einer Iteration?

Question

G = (V, E) - eine gerichtete gewichtete Kurve.

D -> G (w:4) 
D -> C (w:2) 
D -> E (w:2) 
C -> F (w:5) 
C -> A (w:4) 
B -> D (w:3) 
B -> E (w:10) 
G -> F (w:1) 
E -> G (w:6) 
A -> D (w:1) 
A -> B (w:2) 

picture

ich DFS verwenden, um alle einfachen Weg zwischen START zu finden = A Knoten zu END = F Knoten:

def find_all_paths(self, start, end, path=[]): 
     path = path + [start] 
     if start == end: 
      return [path] 
     if start not in self.edges: 
      return [] 
     paths = [] 
     for node in self.edges[start]: 
      if node not in path: 
       paths.extend(self.find_all_paths(node, end, path)) 
     return paths 

Ergebnis:

['A', 'D', 'G', 'F'] 
['A', 'D', 'C', 'F'] 
['A', 'D', 'E', 'G', 'F'] 
['A', 'B', 'D', 'G', 'F'] 
['A', 'B', 'D', 'C', 'F'] 
['A', 'B', 'D', 'E', 'G', 'F'] 
['A', 'B', 'E', 'G', 'F'] 

Ich muss bekommen Ergebnis wie folgt:

['A', 'D', 'G', 'F'], TOTAL_WEIGHT_OF_PATH = 6 
['A', 'D', 'C', 'F'], TOTAL_WEIGHT_OF_PATH = 8 
['A', 'D', 'E', 'G', 'F'], TOTAL_WEIGHT_OF_PATH = 10 
.... 
.... 

Wobei TOTAL_WEIGHT_OF_PATH Summe der Gewichte für jede Kante im Pfad ist. Natürlich konnte ich zählen nur die TOTAL_WEIGHT_OF_PATH Wert nach Ergebnis der DFS bekommen, aber ich brauche es in DFS Schritte für Cutoff-Zustands Suche auf TOTAL_WEIGHT_OF_PATH berechnen

Answer 1

Well (zB TOTAL_WEIGHT_OF_PATH < MAX_WEIGHT_OF_PATH sein sollte), feststellen, dass die TOTAL_WEIGT_OF_PATH (TWOP) an einen beliebigen Knoten V (außer der Wurzel) ist TWOP an den vorhergehenden Knoten U plus das Gewicht der Kante (U, V). TWOP root 0.

TWOP<sub>V</sub> = TWOP<sub>U</sub> + weight(U,V) 

Jedes Mal, wenn auf einem Pfad einen neuen Knoten erweitern, müssen Sie nur die TWOP zu diesem Knoten in sie speichern, so müssen Sie nicht jedes Mal zu berechnen.

Beachten Sie, dass Sie, wenn Sie einen Knoten erneut besuchen und einen anderen Pfad verwenden, ein neues Gewicht berechnen müssen.