问题标签 [longest-path]

我在这里遇到了一些问题。我可以搜索所有目录并将其打印出来，但我找不到最长的路径。这是我的终端统计数据。

14102 1 1 /home/bob/桌面

我只是不知道为什么它不能在这里打印出最长的路径。我只是python的新手，也是一个英语学习者，如果我有任何误解，请告诉我。

更新：我现在可以找到最长的路径，但我不能使用 '~/' 来查找目录。

这是错误消息。

最宽路径和最长路径问题之间有什么区别？更具体地说，为什么前者可以通过找到最大生成树来解决，而后者却不能。我知道在画出最大生成树时，很明显它不一定包含最长的路径，但我无法理解这两个问题之间的差异是什么，这两个问题是真实的。

谢谢。

我有一个有向图（更具体地说，是一个控制流图），每个顶点都有一组属性。

我想找到（或编写）一个算法，给定一个V带有 property的顶点P，找到到某个顶点的最长路径，E这样所有all可能的路径上的顶点V都E包含 property P。

示例 1

假设我有以下图表。（请原谅糟糕的ascii绘图。）

从 开始，始终保持所有可能路径V1的最长路径是-> 。请注意，其他路径，比如-> ，是“有效的”，因为它始终成立，但->是最长的。PV1V7V1V6PV1V7

示例 2

这个例子和上面一样，除了现在P不适用V3：

在这种情况下，从 开始，在所有可能路径中始终V1存在的最长路径是-> 。路径->无效，因为在其中存在一条不成立的路径。PV1V6V1V7V1V7P

关于我的情况的进一步说明

• 该图可以是循环的。
• 该图将是“小到中等”大小，可能有 1000 个或更少的顶点。
• 该图不一定总是有一个根和一个叶，就像我上面的例子一样。

问题

是否有计算此类路径的标准算法？

几天来，我一直在尝试解决一个名为 Sling Blade Runner 的存档ITA 软件难题。谜题的要点如下：

“你能找到多长的重叠电影片名，比如 Sling Blade Runner？”

使用以下电影标题列表：MOVIES.TXT。多字重叠，如“杀死一只知更鸟的许可证”，是允许的。同一个标题不能在一个解决方案中多次使用。可能并不总是产生最多标题的启发式解决方案将被接受：寻求效率和最优性的合理权衡。

MOVIES.TXT文件包含按字母顺序排列的 6561 个电影标题。

我对解决方案的尝试有几个部分。

图表构建：

我所做的是将每个电影标题映射到它可以链接到的每个其他电影标题（在右边）。我最终得到的图表是Map[String, List[String]]. 您可以在此处查看使用此过程构建的图表。

图遍历：

我使用每个节点（地图中的每个键）作为搜索的起始节点进行了深度优先搜索。我跟踪了搜索过程中访问每个节点的深度，并在 DFS 返回的节点中进行了标记。我最终得到的是列表中的List[List[Node]]每一个List[Node]都是来自特定搜索的 DFS 树。

寻找最长的链：

我在上一步中获取了所有图遍历的结果，并且对于每一个List[Node]我都按照我之前标记节点的深度值按降序对列表进行排序。然后从列表的头部开始（这给了我在 DFS 中访问的最深节点），我通过节点回溯以构建一个链。这给了我一个列表中的List[List[String]]每一个List[String]都是该特定 DFS 的最长链的位置。List[List[String]]按每个的大小排序List[String]并抓住头部，然后给了我最大的链条。

结果：

用我的算法找到的最长链是 217 个标题。输出可以在这里查看。

我只能通过谷歌搜索找到其他一些尝试，而且似乎所有其他尝试都产生了比我能够完成的更长的链。例如，这篇文章指出，Eric Burke 发现了一个包含 245 个标题的链条，而Reddit 上名为 icefox 的用户发现了一个包含 312 个标题的链条。

鉴于其他人找到了更长的链，我想不出我的算法在哪里找不到最长的链。非常感谢任何帮助/指导。如果你想查看我的代码，可以在这里找到（它是用 Scala 编写的，我刚开始学习 Scala，如果我犯了一些菜鸟错误，请原谅我）。

更新：

我对我的算法进行了一些更改，现在可以找到长度为 240+ 的链。看这里

我已经使用 R igraph 实现了加权 DAG 的最长路径计算。

对于大图，我的实现（如下所示）很慢。我将不胜感激任何加快速度的提示。也欢迎任何关于我的实现与最知名/典型算法的距离的想法。

谢谢！

我在这里搜索了如何在有向循环图中找到最长的简单路径（简单意味着每个节点只被访问一次，以避免路径无限），并且遇到了这样的解决方案。然而，我发现的所有此类解决方案仅显示如何计算最长路径的长度，而不是该路径中涉及的实际节点。

因此，我的问题是，如何修改这样的算法以提取最长路径中涉及的节点？类似于如何修改 Floyd-Warshall 全对最短路径算法以允许路径重建。

问题：给定一个加权有向无环图 (DAG) 和其中的源顶点 s，找到给定图中从 s 到所有其他顶点的最长距离。

请找到参考图：链接

为什么需要拓扑排序？我们能不能简单地使用来自源顶点的修改后的 BFS。为什么我们如此关心线性排序。

如果这是重复，请把我重定向到相关答案。

谢谢

我有一个无向图，每条边的权重为 1。该图可能有循环。我需要在图中找到最长的路径（每个节点出现一次）。路径的长度是节点的数量。任何简单/有效的解决方案？谢谢！

Okk 作为程序员，我们喜欢参与逻辑构建，但有时我们会因为下面提到的某种谜题而变得空白，情况并非如此。让我声明，这不是任何形式的家庭作业或工作内容，它只是一个逻辑和性能练习难题。Okk 给定字符串s` 的难题，用逗号分隔，例如

现在的关键是找出单词的最长链的长度，例如单词的最后一个字符应该是下一个单词的第一个字符，依此类推，以创建可能的最长链，最后计算该链的长度。

现在我试图找出某种解决方案，例如

1. string用逗号分割
2. 将它们添加到list
3. 排序list 等

但是现在如何开发进一步的逻辑由于我在逻辑开发方面有点差，感谢您的帮助，如果以上一半的逻辑不正确，那么它应该是简单的排序和完美的方法来获得最长的单词链的长度.

摘要
输入：String S= peas,sugar,rice,soup。
输出：4 个单词长度 (peas->sugar->rice->soup) 或 (soup->peas->sugar->rice) 等

我正在尝试解决一个程序，在该程序中，我必须找到给定路线列表连接的最大城市数。

例如：如果给定的路线是[['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] 连接的最大城市，那么4 我无法访问我已经访问过的城市。

我需要想法，比如如何进步。

现在，我的想法是，如果我能够创建一个以城市为键的字典，以及它连接到的其他多少个城市作为它的值，我就会接近解决方案（我希望）。例如：我的字典将{'1': ['2', '11'], '4': ['11'], '2': ['4']} 用于上述给定的输入。如果我遗漏任何东西，我希望得到帮助以进一步进行指导。