CODEWITHSUNDEEP
algorithmgraphcomputer-science
Elimination
Elimination

Reputation: 2723

How to find the sum weight of all edges reachable from some vertex?

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

Now, what I thought about is running topological sort and then starting to run from the last node to the first node (possible by interchanging the direction of the edges)

And then we're evaluating f[v] = f[u] + w(u,v).

but there's a problem; for this graph, we will count f[d] twice. How can I overcome this?

enter image description here

Upvotes: 1

Views: 2250

Answers (2)

Saeid
Saeid

Reputation: 4265

You can use either BFS or DFS to achieve this.

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

Note that we check the visited after total += weight[node][u].

Upvotes: 3

marvel308
marvel308

Reputation: 10458

You can use a bottom up approach. that is firstly calculate the outdegree of each vertex, Now the vertices with 0 outdegree would have F[u] = 0 for them. Now add all such vertices in a queue Q.
Also you would need to store the transpose of the Graph, suppose it was T.

While(!Q.empty){
u=Q.front();
Q.pop();
for all edges E originating from T[u]{
F[v]+=w; (where (u,v) was the edge with w as weight)
//now remove u from the graph
outdegree[v]--;
if(outdegree[v]==0)
Q.push(v);
}
}

Upvotes: 1

Related Questions