这个算法如何在定向非周期图上找到最大路径？

Question

从一段时间以来,我正在使用一个运行在复杂度O(V + E)中的算法,用于在从A点到B点的定向非周期图上找到最大路径,其中包括进行泛洪填充以查找可从中访问哪些节点注意A,以及每个节点有多少"父"(来自其他节点的边).然后,我做了一个BFS但只在我已经使用了所有"父母"时"激活"一个节点.

queue <int> a
int paths[] ; //Number of paths that go to note i
int edge[][] ; //Edges of a
int mpath[] ; //max path from 0 to i (without counting the weight of i)
int weight[] ; //weight of each node

mpath[0] = 0

a.push(0)
while not empty(a)
    for i in edge[a]
        paths[i] += 1
        a.push(i)

while not empty(a)
    for i in children[a]
        mpath[i] = max(mpath[i], mpath[a] + weight[a]) ;

        paths[i] -= 1 ;
        if path[i] = 0
            a.push(i) ;

这个算法有什么特别的名字吗？我把它告诉了一位信息学教授,他只是把它称为"DAG上的最大路径",但是当你说"我用Fenwick树解决了第一个问题,第二个用Dijkstra解决问题,第三个用Dijkstra解决问题时,它听起来不太好最大路径".

Answer 1

正如其他人提到的，这只是“DAG 中的最长路径”。然而，您使用的技术实际上是动态规划的拓扑排序。