有向无环图中两个顶点之间的最大加权路径

Question

喜欢这个问题的一些指导：

G是有向无环图。您要从顶点c移到顶点z。一些优势会减少您的利润，而某些优势会增加您的利润。如何在最大化利润的同时从c变成z。时间的复杂度是多少？

谢谢！

Answer 1

该问题具有最优子结构。c为了找到从顶点到顶点 的最长路径，我们首先需要找到从到 的所有前辈的z最长路径。其中每个问题都是另一个较小的子问题（到特定前驱的最长路径）。czc

z让我们表示as的前身u1,u2,...,uk，并且to 是从到thendist[z]的最长路径.. czdist[z]=max(dist[ui]+w(ui,z))

下面是 3 个前辈省略边集权重的图示：

因此，要找到 的最长路径，z我们首先需要找到到其前辈的最长路径并取最大值（它们的值加上它们的边权重z）。

这要求每当我们访问一个顶点时u，所有的u前驱顶点都必须被分析和计算。

那么问题是：对于任何一个顶点u，如何确保一旦设置dist[u]， dist[u]以后就永远不会改变？换句话说：如何确保在考虑任何源自 的边之前我们已经考虑了从c到 的所有路径？ uu

由于图是非循环的，我们可以通过在图上找到拓扑排序来保证这个条件。拓扑排序就像一个顶点链，其中所有边都从左指向右。因此，如果我们位于顶点，vi那么我们已经考虑了所有通向 的路径vi，并且最终值为dist[vi]。

时间复杂度：拓扑排序需要O(V+E)。在最坏的情况下，z是一个叶子并且所有其他顶点都指向它，我们将访问给出 的所有图边O(V+E)。