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

Question

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

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

Answer 1

naïvem 方法可以贯穿所有可能的顶点排列。

对于每个排列，{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)。