5

一段时间以来，我正在使用一种算法，该算法以复杂度 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 解决了第三个问题时，这听起来并不好最大路径”。

4

3 回答 3

3

正如其他人所提到的，这只是“DAG 中的最长路径”。但是，您使用的技术实际上是使用动态编程进行拓扑排序。

于 2010-05-17T20:37:02.247 回答
2

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

于 2010-05-17T05:54:31.290 回答
1

DAG 中最长的路径？确保你提到 DAG。在一般图中找到最长的路径是 NP-Complete。

于 2010-05-17T05:01:57.600 回答