CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphs
Baekyeon
Baekyeon

Reputation: 57

Algorithm for DAG with weighted vertices

Let G = (V,E) be a DAG (directed acyclic graph). Each vertex v has a weight w(v) assigned to it. Given a vertex u, let f(u) = max{w(v) where v can reach u}. So, in other words, f(u) is the maximum weight among the weights of all vertices that can reach u. The goal is to write a linear time algorithm that computes f(u) for every vertex u in G.

For example, let this be the input graph:

graph

Then the algorithm should compute the following:

Accomplishing this in O(n(n+m)) time is straightforward, but how can this be done in O(n+m) time?

Upvotes: 1

Views: 5413

Answers (1)

Henry
Henry

Reputation: 43728

Do a topological sort, then go through the nodes in this order and assign each node the max of the weight of itself and the f of the immediate predecessors (i.e. nodes that have an edge leading to the current node).

Upvotes: 4

Related Questions