为什么有向无环图中最长路径需要拓扑排序？
问题：给定一个加权有向无环图（DAG）和其中的一个源顶点s，找出从s到给定图中所有其他顶点的最长距离。
请查找参考图：链接
为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们如此关心线性排序。
如果这是重复，请将我重定向到相关答案。
谢谢
共有3个答案
如果你知道如何使用“修改的BFS”，那么你可以这样做。顺便问一句，您打算如何使用“修改后的BFS”？
同时，链接中呈现的算法通过首先对图形进行排序来实现。这就是该算法的设计方式。
现在，拓扑排序顺序由DFS算法在其回溯阶段产生。遗憾的是，DFS 在相反方向上生成拓扑排序顺序。因此，我们无法将最长路径算法的特定处理直接“嵌入”到 DFS 中。（此算法需要向前处理。因此，我们必须采用双通道方法：首先执行纯DFS，构建完整的转置序列，然后进行第二次传递以找到最长的路径。
在许多现实生活中，基于toposort的算法很有价值，因为DAG的顶点可能已经以toposorted的顺序存储。例如，toposorting在预处理阶段只完成一次。之后，各种基于toposort的算法有效地变成了非常高效的一次性算法，无需额外的内存要求（与BFS或DFS等算法相反，它们的堆栈、队列等需要额外的内存）
如果我们能够跟踪访问的节点，那么应该可以使用递归DFS和一些记忆。
从起始节点开始。对于每个邻居，计算(邻居到邻居的距离邻居到目标的距离)。取其中的最大值，记为这个节点的最大值，然后返回。
基本上，如果你知道从你的邻居到目标的最大距离，你就知道从你到目标的最大距离。如果你记住，你不会多次访问任何节点。
如果我们不对它进行排序，我们不知道首先选择哪个相邻顶点，这可能会导致我们使用顶点v的距离来更新其相邻顶点的距离adj[v]的情况，但是在那之后，顶点v的距离会更新，因此来自adj[v]的顶点也可以获得更大的距离， 但我们不会再去拜访他们了。
-
如何输出有向无环图的所有可能的拓扑排序？例如，给定一个图形，其中 V 指向 W 和 X，W 指向 Y 和 Z，X 指向 Z： 如何对此图进行拓扑排序以产生所有可能的结果？我能够使用广度优先搜索来获得V，W，X，Y，Z，并使用深度优先搜索来获得V，W，Y，Z，X。但无法输出任何其他种类。
-
解决这个问题的正确方法是什么？还能在线性时间内求解吗？
-
是否有一种算法，在给定一个未加权有向无环图的情况下，将所有节点排序到一组节点列表中，从而 保留拓扑顺序（即，对于所有边
-
我想在有向（无环）图中找到最长的路径。假设我知道起始节点-汇。路径应该从这一点开始。我在想我可以将边的权重设置为-1。有很多方法可以找到所有最短的路径，但你必须通过终点。有没有可能得到最短的路径（无论最终节点如何）？ 假设我想为节点 nr 1（汇）找到最长路径。所以这个算法给了我1-2-3-4-5-6。
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关