带加权顶点的 DAG 算法

Question

设 G = (V,E) 为 DAG(有向无环图)。每个顶点 v 都有一个分配给它的权重 w(v)。给定一个顶点 u，让 f(u) = max{w(v) where v can reach u}。所以，换句话说，f(u)是所有能到达u的顶点的权值中最大的权值。目标是编写一个线性时间算法，为 G 中的每个顶点 u 计算 f(u)。

例如，假设这是输入图:

然后该算法应计算以下内容:

• f(A) = 5
• f(B) = 12
• f(C) = 15
• f(D) = 12
• f(E) = 12

在 O(n(n+m)) 时间内完成这个很简单，但是如何在 O(n+m) 时间内完成呢？

Answer 1

进行拓扑排序，然后按此顺序遍历节点，并为每个节点分配其自身权重的最大值和直接前置节点的 f(即具有通往的边的节点当前节点)。