如何在一次迭代中计算DFS中有向加权图路径的总权重？

Question

G = (V,E) - 有向加权图。

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

我使用 DFS 找到 START=A 节点到 END=F 节点之间的所有简单路径：

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

结果：

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

我需要得到这样的结果：

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

其中 TOTAL_WEIGHT_OF_PATH 是路径中每条边的权重之和。当然我可以在得到 DFS 的结果后只计算 TOTAL_WEIGHT_OF_PATH 值，但是我需要将它计算到 DFS 步长中以便在基于 TOTAL_WEIGHT_OF_PATH 的条件下搜索截止值（例如 TOTAL_WEIGHT_OF_PATH 应该是 < MAX_WEIGHT_OF_PATH)

Answer 1

嗯，注意 TOTAL_WEIGT_OF_PATH (TWOP) 到任何节点 V（除了根）是 TWOP 到前面的节点 U 加上边的权重（紫外线）。 TWOP 到 root 是 0.

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

任何时候在一条路径上扩展一个新的节点，只需要将TWOP到这个节点存进去即可，不用每次都计算

注意，如果你再次访问一个节点，使用不同的路径，你需要"calculate"一个新的权重。

如何在一次迭代中计算DFS中有向加权图路径的总权重？

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

algorithm

graph-theory

depth-first-search

graph-algorithm