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

Question

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

algorithmgraphlongest-path

6

我知道对于非定向图来说，这个问题是NP完全难题，因此我们应该使用Brute Force来检查所有可能的路径。我们怎样做呢？请提供一个伪代码并告诉我算法的复杂度。

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

伪代码：

1. 初始化最短路径为无穷大 2. 遍历所有可能的路径 3. 对于每一条路径： 3.1 计算路径长度 3.2 如果路径长度比当前最短路径小，则更新最短路径 4. 返回最短路径

时间复杂度：O(2^n) ，n为节点数。

优化方法：

1. 剪枝：当我们发现当前路径已经长于当前最短路径时，可以直接放弃搜索，即剪枝。 2. 动态规划：记录子问题的解，避免重复计算。

- Narek

2

你必须加入额外的限制条件，否则路径会无限延伸... - hivert

2

每个顶点只在路径中出现一次 - 这是一条简单路径。 - Narek

1

仅仅因为它是NP完全问题，并不意味着你应该使用蛮力算法。当然，在最坏情况下，你无法做得比指数时间更好，但最坏情况很少出现。例如，有成千上万个子句和变量的3-SAT实例以及有成千上万个城市的TSP实例通常都能够被解决，而且明显不是通过蛮力算法求解的。 - harold

无权重：https://dev59.com/83E85IYBdhLWcg3w9ohJ - Ciro Santilli OurBigBook.com

2个回答

4

如果你的图是一个特殊情况，即有向无环，你可以采用动态规划方法，例如此处所述的方法。你需要按拓扑排序对图进行排序，然后按照拓扑顺序，对于每个节点V，检查其所有相邻节点并更新它们的“距离”值（如果比已经存储的“距离”大，则进行更新，否则不变）。

否则，在一般情况下，该问题确实属于NP完全问题，因为它归约为汉密尔顿回路问题。一种解决方法是对所有边取反，并尝试使用 Bellman-Ford 算法。但要注意，它不适用于负循环。

- webuster

无向无环图呢？它是否仍然是NP完全问题？ - Sush

无向无环图是一棵树，因此问题是找到树的直径，这可以在线性时间内完成。 - Megadardery

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

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

- AlexD · Accepted Answer

一种天真的方法是遍历所有可能的顶点排列。对于每个排列{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)。