有向无环图中最长路径为什么需要拓扑排序？

Question

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

请找到参考图：链接

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

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

谢谢

Answer 1

如果我们不排序，我们不知道首先选择哪个相邻顶点，这可能会导致我们使用顶点

v

的距离来更新其相邻顶点

adj[v]

的距离的情况，但是之后也就是说，顶点

v

的距离会更新，因此来自

adj[v]

的顶点也可以获得更大的距离，但我们不会再访问它们了。

基于您引用的图表的示例（http://www.geeksforgeeks.org/wp-content/uploads/LongestPath.png）：
我们在这一步说：

比方说，我们从顶点“0”开始遍历图，并选择距离为

6

的顶点（而不是距离为

2

的顶点，如果我们使用拓扑顺序，我们就会选择该顶点）。已处理的顶点为绿色，当前正在处理的顶点为红色：

我们已将最后一个顶点的距离更新为

7

并且不会增加它，但是如果我们在上一步中访问了距离为

2

的顶点，则该顶点的距离将为 10：

Answer 2

如果我们可以跟踪访问过的节点，那么应该可以使用递归 DFS 和一些记忆。

从起始节点开始。对于每个邻居，计算（到邻居的距离 + 邻居到目标的距离）。取其中的最大值，将其记忆为该节点的最大值，然后返回它。

基本上，如果您知道从邻居到目标的最大距离，您就知道从您到目标的最大距离。如果你记住了，你就不会多次访问任何节点。

Answer 3

如果每次更新时都贪婪地处理节点，则不需要拓扑排序。如果你贪婪地重新访问所有邻居，你可以提高最长的距离。例如在 9 处，您可以检查 9+1 > 7 并重新访问第 7 个节点来更新它。

Answer 4

如果你知道如何使用“改进的 BFS”来做到这一点，那么你就可以这样做。顺便说一句，你建议如何使用“改进的 BFS”来做到这一点？

同时，链接中提供的算法首先对图进行拓扑排序。这就是该算法的设计方式。

现在，拓扑排序顺序是由DFS算法在回溯阶段产生的。不幸的是，DFS 会以reverse 方向生成拓扑排序顺序。为此，我们不能将最长路径算法的具体处理直接“嵌入”到DFS中。 （该算法需要在forward方向上进行处理。）因此我们必须采用两遍方法：首先进行纯DFS，构建完整的拓扑排序序列，然后进行第二遍以找到最长路径。

在许多现实生活中，基于拓扑排序的算法很有价值，因为 DAG 的顶点可能已经按拓扑排序顺序存储。 IE。拓扑排序仅在预处理阶段进行一次。之后，各种基于拓扑排序的算法有效地转变为非常高效的单遍算法，无需额外的内存需求（与 BFS 或 DFS 等算法相反，它们的堆栈、队列等需要额外的内存）

Answer 5

基本上，使用拓扑排序可以让我们更快地找到解决方案。存在一些算法可以找到此类问题的解决方案，例如迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）、旅行推销员等问题，但使用它们的复杂性对于大范围的输入来说会变得很大风险。使用拓扑排序的一般直觉是给定一个 DAG 直接无环图。按照指示，我们必须使用拓扑排序来访问排序中的节点，才能实现我们需要遍历的图的排序，并且它是非循环的。但当我们想要放宽节点与源的距离时，主要的症结就出现了。拓扑排序帮助我们找到必须放松的顺序。