线性时间中有向无环未加权图中的最长路径

Question

如何在线性时间内找到像这样的图表中的最长路径：

3 -> 2

4 -> 3

2 -> 5

我知道这里最长的路径是 4 -> 3 -> 2 所以它有 3 个 veticles，但我不知道如何在 O（N） 时间内找到它。请帮忙。提前谢谢你。

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) 

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

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