How to calculate total weight of paths of directed weighted graph in DFS in one iteration?

Question

G = (V,E) - a directed weighted graph.

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

I use DFS to find all simple path between START=A node to END=F node:

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

Result:

['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']

I need to get result like this:

['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
....
....

Where TOTAL_WEIGHT_OF_PATH is sum of weights for each edge in path. Of course I could just count the TOTAL_WEIGHT_OF_PATH value after getting result of DFS, but I need to calculate it into DFS steps for cutoff searching in condition based on TOTAL_WEIGHT_OF_PATH (e.g. TOTAL_WEIGHT_OF_PATH should be < MAX_WEIGHT_OF_PATH)

Fila Fila · Accepted Answer · 2016-04-22T09:19:16

Well, notice that the TOTAL_WEIGT_OF_PATH (TWOP) to any node V (other then the root) is TWOP to the preceding node U plus the weight of the edge (U,V). TWOP to root is 0.

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

Any time you are expanding a new node on a path, you just need to store the TWOP to this node into it, so you don't need to calculate it every time.

Note, that if you visit a node again, using different path, you need to "calculate" a new weight.

How to calculate total weight of paths of directed weighted graph in DFS in one iteration?

1 Answers