这个用于寻找有向无环图上最大路径的算法叫做什么？

Question

这个用于寻找有向无环图上最大路径的算法叫做什么？

5

最近我使用了一种复杂度为O(V+E)的算法，用于在从点A到点B的有向无环图中找到最大路径。这个算法是通过洪水填充(flood fill)来确定从节点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 Tree解决了第一个问题，用Dijkstra解决了第二个问题，用最大路径解决了第三个问题”时，这听起来不太好。

- Martín Fixman

3个回答

2

可能不行 - 因为这不是一种常见的算法。当您需要在DAG中查找路径时，只需对其进行排序，遍历一次并保留最长路径即可。

- ima

1

有向无环图中的最长路径？确保提到DAG。在一般图中找到最长路径是NP完全问题。

- Aryabhatta

我猜的没错，我只是想要一个欧洲科学家的响亮名字。 - Martín Fixman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Larry · Accepted Answer

这只是“有向无环图中最长路径”问题，正如其他人所提到的。然而，你使用的技术实际上是拓扑排序和动态规划。