问题：给定一个加权有向无环图 (DAG) 和其中的源顶点 s，找到给定图中从 s 到所有其他顶点的最长距离。
请找到参考图：链接
为什么需要拓扑排序？我们能不能简单地使用来自源顶点的修改后的 BFS。为什么我们如此关心线性排序。
如果这是重复，请把我重定向到相关答案。
谢谢
问问题
9350 次
4 回答
16
If we don't sort it, we don't know which adjacent vertex to choose first and it may lead to a situation where we use distance of a vertex v to update distances of its adjacent vertices adj[v], but after that, the distance of vertex v gets updated, so vertices from adj[v] could also get bigger distances, but we won't visit them anymore.
Example based on the graph you have referenced (http://www.geeksforgeeks.org/wp-content/uploads/LongestPath.png):
Let's say that at this step:
Say, we start to traverse the graph from vertex '0', and we choose vertex with distance 6 (instead of vertex with distance 2, which we would have chosen if we had used topological order). Already processed vertices are green, vertex currently being processed is red:
We have updated the distance of the last vertex to 7 and we won't increase it, however if we had visited vertex with distance 2 in previous step, the distance of this vertex would have been 10:
于 2014-12-30T20:35:30.313 回答
4
如果我们可以跟踪访问过的节点，那么应该可以使用递归 DFS 和一些记忆。
从起始节点开始。对于每个邻居，计算（到邻居的距离 + 从邻居到目标的距离）。取其中的最大值，将其记为该节点的最大值，然后返回。
基本上，如果你知道你的邻居到目标的最大距离，你就知道你到目标的最大距离。如果你记忆，你不会多次访问任何节点。
于 2016-02-17T01:31:17.153 回答
0
如果您知道如何使用“修改后的 BFS”来做到这一点，那么您可以这样做。顺便说一句，您如何建议使用“修改后的 BFS”来做到这一点？
同时，链接中介绍的算法通过首先对图进行拓扑排序来实现。这就是该算法的设计方式。
现在，拓扑排序顺序是由 DFS 算法在其回溯阶段生成的。不幸的是，DFS 以相反的方向生成拓扑排序顺序。因此，我们不能将最长路径算法的具体处理直接“嵌入”到 DFS 中。（该算法需要正向处理。）因此我们必须采用两遍方法：首先进行纯DFS，构建完整的拓扑排序序列，然后进行第二遍以找到最长的路径。
在许多现实生活中，基于拓扑排序的算法很有价值，因为 DAG 的顶点可能已经以拓扑排序的顺序存储。即拓扑排序在预处理阶段只进行一次。之后，各种基于拓扑排序的算法有效地变成了非常有效的一次性算法，不需要额外的内存（与 BFS 或 DFS 等算法相反，它们的堆栈、队列等需要额外的内存）
于 2016-02-17T01:42:01.990 回答
0
如果您在每次更新发生时都贪婪地处理节点，则不需要拓扑排序。如果您贪婪地重新访问所有邻居，您可以改善最长距离。例如在 9，您可以检查 9+1 > 7 并重新访问第 7 个节点以更新它。
于 2018-11-11T21:51:30.437 回答