如何找到DAG中的两个顶点之间的最大权重路径？ [英] How to find the maximum-weight path between two vertices in a DAG?
问题描述
在一个DAG G，非负加权边，你如何找到G中两个顶点之间的最大权重路径？
In a DAG G, with non negative weighted edges, how do you find the maximum-weight path between two vertices in G?
感谢你们！
推荐答案
您可以在O解决这个（N + M）用拓扑排序的时间（其中n为节点的数量，M边的数量）。通过做拓扑排序的反向曲线开始，让你的方式，使得没有节点是其所有的孩子都到过访问下令所有节点。
You can solve this in O(n + m) time (where n is the number of nodes and m the number of edges) using a topological sort. Begin by doing topological sort on the reverse graph, so that you have all the nodes ordered in a way such that no node is visited before all its children are visited.
现在，我们将标记所有具有最高权重的路径开始与该节点的权重的节点。这是基于上完成以下递归观察：
Now, we're going to label all the nodes with the weight of the highest-weight path starting with that node. This is done based on the following recursive observation:
- 最高重量路径从汇聚节点（没有出边的任何节点）开始的重量是零，因为从该节点出发的唯一途径就是这样节点的长度为零路径。
- 最高重量路径从任何其他节点开始的重量是通过以下的传出边缘至一个节点，则取最大权重的路径从该节点形成的任何路径的最大重量给出。
由于我们的节点反向拓扑排序，我们可以访问所有的节点，在保证一个订单，如果我们曾经尝试以下的边缘，查找最重的路径的成本在那个节点的终点，我们将已计算出的最大权重路径起始于该节点。这意味着，一旦我们有相反的拓扑排序的顺序，我们可以运用以下算法到所有节点的顺序：
Because we have the nodes reverse-topologically sorted, we can visit all of the nodes in an order that guarantees that if we ever try following an edge and looking up the cost of the heaviest path at the endpoint of that node, we will have already computed the maximum-weight path starting at that node. This means that once we have the reverse topological sorted order, we can apply the following algorithm to all the nodes in that order:
- 如果该节点没有出边，记录最重的路径的重量在那个节点开始（记为D（U））为零。
- 否则，对于每个边（u，v）的离开当前节点u，计算升（U，V）+ D（v）中，并且将d（u）的是达到这样的最大值。
一旦我们做到这一步，我们就可以做最后一次传过来的所有节点，并返回的D任何节点达到了最高值。
Once we've done this step, we can make one last pass over all the nodes and return the highest value of d attained by any node.
这种算法的运行时间可如下进行分析。计算拓扑排序可以在O使用许多不同的方法来实现（N + M）的时间。当我们再扫描过的每个节点，每个节点的每个出边，我们访问每个节点和边一次。这意味着，我们花O（n）时间的边缘节点和O（米）时间。最后，我们花O（n）的时间上最后一个传过来的元素来找到权重最高的路径，这需要为O（n）。这给出了一个总计O（N + M）时间，这是线性输入的大小。
The runtime of this algorithm can be analyzed as follows. Computing a topological sort can be done in O(n + m) time using many different methods. When we then scan over each node and each outgoing edge from each node, we visit each node and edge exactly once. This means that we spend O(n) time on the nodes and O(m) time on the edges. Finally, we spend O(n) time on one final pass over the elements to find the highest weight path, which takes O(n). This gives a grand total of O(n + m) time, which is linear in the size of the input.
这篇关于如何找到DAG中的两个顶点之间的最大权重路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
