问题标签 [longest-path]

在这棵树中：

从根开始的最长路径是a-d-f-g

这是我的尝试：

函数中的树main()不是我展示的示例。对于这棵树，预期的结果是a-c-f。这棵树如下图所示：

现在，我明白了

None由于我有基本案例，我不确定那里是如何出现的。

谢谢！

以平面的正方形拼贴为例，想象一个有限的、连接的和简单连接的拼贴子集 D。D 当然也可以通过为每个图块取一个节点并连接相邻节点来解释为方形网格的特定子图。

假设我在 D和D 的边界中有一个起始节点/图块 A 和一个结束图块 B。

是否有一种简单、直接的算法可以在 A 和 B 之间的 D 中找到相当长的自回避路径？

我发现了有关寻找绝对最长路径的文献，以及次优算法，虽然性能非常好，但看起来非常复杂。我想知道是否存在足够好的驯服算法。

我在这里唯一的想法是计算通过 A* 的最短路径，然后通过横向“折叠”来扭曲它以填充尽可能多的空间，但我不确定这是否是个好主意。

另一个想法是是否有一个几乎愚蠢简单的“扫描线”模式填充 A 和 B 之间的空间，因此对于“矩形”D 表现良好。我怀疑这存在，但我找不到它。

我正在编写一个程序来查找来自标准输入的 DAG 的最长路径。我终于让它编译了，它说由于我的数组列表，它正在使用未经检查或不安全的操作，但我得到了一个索引边界错误，感觉就像我已经尝试更改每个循环，我一定会遗漏一些东西，在此感谢任何提示。这是我的代码：

使用当前代码编辑 1 这是错误：

我知道最长/最短路径可以通过“按拓扑顺序处理顶点，并将每个顶点的路径长度计算为通过其任何传入边获得的最小或最大长度”来在线性时间内找到，或者把它更简洁，拓扑排序并找到关键路径。

我的问题是我需要添加另一个限制，即有效路径中的最大边数。这使事情变得复杂，因为节点的“通过其任何传入边获得的最大长度”可能涉及更多边，这意味着由于已经达到最大边，因此可能不再可以到达更高权重的节点。

解决这个问题的正确方法是什么？它仍然可以在线性时间内解决吗？

我正在尝试找到一种方法来解决具有以下特征的图的最长路径问题：

• 导演
• 加权（包括负权重）
• 不是无环的，虽然我只是在寻找简单的路径。

在过去的两天里，我第一次看了一下 Boost.Graph。它看起来很复杂，我想确保在深入研究文档以发现我实际上无法使用它之前，我可以用这个库解决我的问题。

那么我可以使用 Boost.Graph 来解决我的问题吗？它甚至可能是NP-Complete吗？即使我可以使用 Boost.Graph，是否有更好的基于性能的替代方案？

我有一个图形，它保存为两个表，名称为 Edge 和 Node，在 SQL 中如下所示：

例如，从节点 10 到节点 12 的路径的一种可能解决方案如下：

现在，我想找出图形节点之间的最长路径（对于任何可能的路径）。

我用负边缘改变了dijkstra，它循环了，不返回任何结果。

是否有任何程序或算法来找出所需的结果？

有一个二维数组long[50][50]，其中填充了从 0 到 100 的随机数。我需要找到从最大（或第一个最高）到最小的最长路径。您可以向上、向下、向左和向右移动。

我找到了如何找到单一方式：找到最大的最近数字（但不是更大，就是这样）并移动到那里。

我的搬家方法：

找到最近的最大：

然后仅使用最近的最大值找到最长的方式：

的大小way将是此类路线的长度。但是现在我不知道如何从某个坐标中找到所有可能的路线以找到其中最长的路线。我的意思是我不知道回到“分叉”并继续另一条路线的最佳方式是什么。

我希望解释清楚。提前致谢。

从某个顶点开始，如何找到相对于该顶点的最长路径？我一直在浏览，但找不到这个问题的解决方案，它实际上适用于所有可能的 DAG 案例。NetworkX 中的源代码将是首选，但常规 python 也可以。我真的很好奇为什么我无法找到任何合适的工作示例，我确实理解这是一个 NP 类型的问题，但我想知道最有效的方法。

我在下面创建了一个简单的图表

所以我们有两条可能的路径

所以最长的路径是前者

有没有一种简单的方法来收集最长的路径，A->B->D->F？

给定：一个未加权的有向图 (G=(E,V))，它可以包含任意数量的循环。

目标：对于所有顶点，我想要到 V 中某个目标顶点 X 的最长简单路径

算法思路：

这对所有情况都正确吗？（假设可以从每个顶点到达目标）

我的图中的边数非常少。假设 |E| <= 3*|V| 持有。我将如何计算平均时间复杂度？

谢谢！