dag中最长路径的算法设计,写出bellman方程和伪代码,并分析时间复杂度。

dag中最长路径的算法设计是基于Bellman-Ford算法的变体。该算法可以解决有向无环图中的最长路径问题。

首先，我们需要定义一个数组d[]，表示从起点到每个顶点的最长路径长度的估计值。然后，我们从起点开始遍历所有顶点，初始化d[]为负无穷大。

接下来，我们对所有的边进行松弛操作。即，对于边(u, v)，如果d[v] < d[u] + weight(u, v)，则更新d[v] = d[u] + weight(u, v)。

重复进行V-1次（V是图的顶点数）上述的松弛操作。

伪代码如下：

function longestPath(dag, start):
    initialize d[] with -INF
    d[start] = 0
    
    for i in range(V-1):
        for each edge (u, v) in dag:
            if d[v] < d[u] + weight(u, v):
                d[v] = d[u] + weight(u, v)
    
    return d

时间复杂度分析：
最坏情况下，算法要遍历所有的边V-1次，对每条边进行一次松弛操作。所以总的时间复杂度为O(V*E)，其中V表示图的顶点数，E表示图的边数。