algorithm - 如何在图中找到最长的简单路径？

Question

我知道对于无向图，这个问题是 NP 完全的，因此我们应该使用蛮力来检查所有可能的路径。我们怎么能做到这一点？请提出一个伪代码并告诉我该算法的复杂性。

如果有优化，那就太棒了！

Answer 1

一种简单的方法可以遍历所有可能的顶点排列。

对于每个排列{v1, ..., vN}，您检查是否可以从v1到v2，然后从v2到v3等。如果可以，将相应的边长添加到当前路径长度。如果不是，则进行下一个排列。

最长的此类路径就是您的答案。

---

或者，您可以使用递归来做几乎相同的事情。

path = 0
bestPath = 0
used = new bool[N] // initialize with falses
for(u = 0; u < N; u++)
    Path(u); // build paths starting from u
print bestPath

在哪里

Path(u)
    used[u] = true
    foreach v in neighborhood(u)
        if(!used[v])
            path += distance(u, v)
            bestPath = max(bestPath, path)
            Path(v)
            path -= distance(u, v)
    used[u] = false

时间复杂度是可怕的O(N * N^N)。

Answer 2

如果您的图是有向和非循环的特殊情况，您可以使用动态编程方法，例如此处描述的方法。你基本上对你的图进行拓扑排序，然后按拓扑顺序，对于每个节点 V，检查它的所有邻居并更新它们的“距离”值，如果它大于已经记住的“距离”（用 -infinity 或其他东西初始化）。

否则，在一般情况下，问题确实是 NP 完全的，因为它简化为哈密顿循环。您可以做的一件事是否定所有边缘并尝试 Bellman-Ford 算法。但是请注意，这对负循环不利。