algorithm - 如何找到从某个顶点可达的所有边的总权重？

Question

Consider a directed graph with no cycles. I need to find for each u the total weight of edges reachable from u (by reachable we mean there's a path from u to some v).

现在，我想到的是运行拓扑排序，然后从最后一个节点开始运行到第一个节点(可能通过互换边的方向)

然后我们计算 f[v] = f[u] + w(u,v)。

但是有一个问题；对于此图，我们将计算 f[d] 两次。我怎样才能克服这个？

Answer 1

您可以使用 BFS 或 DFS 来实现这一点。

total = 0
dfs (node):
  if visited[node] == 1:
      return
  visited[node] = 1
  for all u connected to node:
      total += weight[node][u]
      dfs(u)

请注意，我们在 total += weight[node][u] 之后检查访问量。