有向无环图中的最长路径

Question

为了在DAG（有向无环图）中找到最长路径，我知道两种算法：算法1：对排序结果使用动态规划 + 进行拓扑排序。或者算法2：使用深度优先搜索枚举DAG中的所有路径，并记录最长路径。似乎使用DFS枚举所有路径的复杂度比算法1要好，这是真的吗？

- Frank

---

相关问题请参考[CS.SE]: 在DAG中查找两个顶点之间的最短路径和最长路径。 - Palec

Answer 1

你的第二个选项是不正确的：DFS并不会探索所有可能的路径，除非你的图是一棵树或者森林，并且你从根节点开始。我知道的第二个算法是将权重取反并找到最短路径，但它比你列为#1的拓扑排序+DP算法要慢一些。

- Sergey Kalinichenko

---

好的，我的意思是使用重启动的DFS算法，从之前没有被访问过的任何一个顶点开始进行深搜。这样可以遍历整个有向无环图（DAG）。这难道不比拓扑排序+动态规划更快吗？ - Frank

@Frank 如果使用从未访问过的顶点重新启动的DFS将无法探索所有路径。考虑一个图A->B->C；你从B开始DFS，到达C并停止；然后从A重新开始，到达B并再次停止，因为你已经访问了C。DFS找到的两条路径，B-C和A-B，长度都为1；最长的路径A-B-C长度为2。 - Sergey Kalinichenko

即使您从源头开始，也要考虑一个带有钻石形的图表：A->B,C ; B->D ; C->D ; D->E,F ; E->G ; F->G。 A是源，因此您从它开始探索。 您走过 A-B-D-E,G，回到 D，尝试 A-B-D-F-G，回到 A，尝试 A-C-D，并停止，因为现在已经完全探索了 D。 如果按权重计算的最长路径是 A-C-D-E-G，则深度优先搜索无法找到它。 - Sergey Kalinichenko

@Thomash 所有的树都是有向无环图，但并非所有的有向无环图都是树。 - Sergey Kalinichenko

@dasblinkenlight 是一种在有向无环图上进行深度优先搜索的算法，它通过计算当前节点与其子节点中权重和最大的路径来寻找最长路径。可以说这是一种伪装成动态规划的算法。 - Rabih Kodeih

Answer 2

使用“深度优先搜索”列举有向无环图(DAG)中的所有路径：

import numpy as np

def enumerate_dag(g):

    def enumerate_r(n, paths, visited, a_path = []):
        a_path += [n]
        visited[n] = 1
        if not g[n]:
            paths += [list(a_path)]
        else:
            for nn in g[n]:
                enumerate_r(nn, paths, visited, list(a_path))

    paths, N = [], len(g)
    visited = np.zeros((N), dtype='int32')

    for root in range(N):
        if visited[root]: continue
        enumerate_r(root, paths, visited, [])

    return paths

- Frank

---

你尝试过将双钻石图传递给这段代码吗？看起来它有50/50的机会错过最长路径。 - Sergey Kalinichenko

我刚刚尝试了以下内容：[[1,2]，[3]，[3]，[4]，[5,6]，[7]，[7]，[8]，[9]，[]]。 我得到了4条路径：[[0，1，3，4，5，7，8，9]，[0，1，3，4，6，7，8，9]，[0，2，3，4，5，7，8，9]，[0，2，3，4，6，7，8，9]]，我相信这是正确的答案。就我所知（从许多其他测试中），此算法正确枚举DAG中的路径。拓扑排序基于DFS的非常类似的用法。只要你在源处开始/重新启动，DFS将探索从每个源可达的所有节点，因此上面的代码完全探索了DAG，没有遗漏任何顶点。 - Frank

我误解了你代码中 visited 的使用：你设置了它，但没有用它来决定是否应该继续遍历。这不是所谓的深度优先搜索，因为DFS不会访问已经完全探索过的节点。DFS和你的代码之间最大的区别在于，你的代码效率极低。尝试重复相同的钻石图案五十次，你就会知道我的意思：你的程序将探索所有 2^50 条路径，这是非常多的路径需要探索。 - Sergey Kalinichenko

@dasblinkenlight DAG的探索策略是“DFS”：它会扩展每个路径到汇点，然后回溯。至于“非常低效”，这个函数的目的是枚举所有路径。因此，它必须多次访问某些节点。 - Frank

但是我可以看出，枚举所有路径以找到最长路径与拓扑排序+排序相比，复杂度会很高。 - Frank

Answer 3

不需要深度优先搜索。 算法：输入一个有向无环图G。 每条弧都持有一个变量E。

for each node with no predecessor :
    for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
    for each of his leaving arcs, E=max(E(entering arcs))+1.

当所有节点被处理完成时，max_path是边缘中最高的E。

- Pyra

---

这是正确的答案，请参见https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths。 - Diomidis Spinellis