graph - longest path in directed acyclic unweighted graph in linear time

Question

how can I find in linear time the longest path in a graph like this one:

3 -> 2

4 -> 3

2 -> 5

I know that the longest path here is 4 -> 3 -> 2 So it has 3 veticles but i dont know how to find it in O(N) time. Please help. thank you in advance.

Answer 1

对图进行顶部排序并按拓扑排序顺序选择顶点。

For each vertex u
    For each edge (u,v)
       if(d[v] < d[u] + weight(u,v))
          d[v] = d[u] + weight(u,v) 

其中，对于任何顶点 u，d[u] 是距源的最长距离。对于每个顶点 u，d[u] 被初始化为最小值并且 d[source]=0。

由于它是一个 DAG，因此我们只需要遍历和放松每个边一次。它基本上是简化了最长路径的贝尔曼福特算法。