问题标签 [longest-path]

我需要在树中找到最长的 ROOT 到 LEAF 路径。我已经有代码可以找到最短的根到叶子，我想知道我是否可以以任何方式重用它来找到最长的路径。

所以这是我用来查找最短路径并将其存储在向量中的代码。这些是一个类的成员。

有什么办法可以修改并重用它？还是你认为我必须重新开始？谢谢 ：）

此代码适用于小型网络（30 个顶点），但对于 300 个顶点的网络需要数小时！有更快的方法吗？

我知道要证明任何问题都是 NP 完全的，你必须证明

1. 它在NP中。

2. 这是NP难的。

我知道如何证明无向无权图中的最长路径，但对于加权图，我完全不知道；如何证明它 NP-hard 和 NP。

实际上给定的问题说“证明问题'找到给定的无向加权图具有包含总权重> = K的最长路径'”

令 G = (V, E) 为无向加权图，K 为正整数。

给定一个网格大小（ ），如何在开始（ ）和结束（ ）点m*n之间生成随机路径，并附加条件是随机路径覆盖所有节点x1, y1x2, y2

例如

• 5*6 网格
• 起点 -> (1, 1)
• 终点 -> (1, 6)

可以使用什么方法生成从 (1, 1) 开始并在 (1, 6) 结束的随机路径，并且该路径经过剩余的 28 个节点？

Dijkstra 不能用于最长路径，因为它使用当前最短路径肯定比其他路径之一短的属性。当然，这是正确的，假设没有负边权重。这个概念也是最长路径在 Dijkstra 上不起作用的原因，因为当前最长的路径并不能保证以后不会有另一条更长的路径采用更大的值。

另一方面，Bellman Ford 以较差的性能提供了负权重的灵活性。这意味着对于贝尔曼福特来说，它不适用于与 Dijkstra 相同的贪婪属性。所以这就是为什么我很困惑 - 为什么贝尔曼福特不能用于单源最长路径问题（NP 难）？例如，我们可以简单地将图的所有权重乘以 -1 并找到最短路径，这将是原始图的最长路径。

鉴于这个代表一棵树的类，我对如何返回一个包含作为树高度一部分的节点的列表有点困惑。

我正在谈论的函数是“LongestPathNodes”函数，我认为它必须是递归的，我写了其中的一部分，但我对如何进行感到困惑，因为树不必是一个二进制的。

我有一个图表，其中显示了朋友和他们居住的城市的联系。朋友的联系用黑色箭头表示，城市的联系用虚线表示。我想得到住在一个共同城市的朋友的最长路径，在 A 先生和 D 先生之间。答案是路线：A-> B-> E-> D。应该为它写什么查询?

我最近通过两次使用 BFS 解决了最长路径的问题。我还了解到动态规划可用于求解有向无环图中的最长路径。给定使用动态编程的随机节点，伪代码和递归方程/运行时用于在无向加权树中查找最长路径是什么？

有没有一种有效的方法来删除不属于 DAG 中两个节点之间最长路径的所有边？例如，对于图（DAG）： (1->2, 2->3, 2->4, 1->3, 1->4) 我想删除边 1->3, 1-> 4 因为路径 1->2->3, 1->2->4 更长

编辑：所以我认为最好的方法是使用拓扑排序并从右到左遍历数组，同时为每个节点聚合其后代。然后对于每个边 a->b，我们可以使用 a 的所有其他直接后代检查 b 是否可以从 a 到达（如果是，我们删除边）。但我没有找到一个实现，我不确定它是否正确，有没有人知道这样的实现？

我有一个关于如何在具有简单边且边没有权重的无向图中找到最短路径和最长路径的一般问题。

我们需要使用 DFS 算法找到图中的最长路径，而我们需要使用 BFS 算法找到图中的最短路径，这是一个正确的结论吗？

我知道，当我们使用 BFS 时，我们会逐层访问节点，并且可以将其用于最短路径查找（这可能是 Dijkstra 基于 BFS 或类似于 BFS 的原因）。但我看不出我们可以如何有效地找到使用 BFS 的最长路径。有人可以详细说明吗？

另外，我知道使用 DFS 查找最长路径可能效率不高，我们可能需要使用动态编程思想来提高时间复杂度，但为了讨论的功能，我们忽略它。