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

Question

希望能够为您提供以下问题的指引：

G是一张有向无环图，您希望从顶点c移动到顶点z。其中有些边降低了您的利润，而有些则增加了您的利润。如何在最大化利润的同时从c到达z？时间复杂度是什么？

谢谢！

- evenodd

Answer 1

这个问题具有最优子结构。为了找到从顶点c到顶点z的最长路径，我们首先需要找到从c到所有z的前任的最长路径。每一个子问题都是另一个更小的子问题(从c到特定前任的最长路径)。

让我们将z的前任表示为u1,u2,...,uk，将dist[z]表示为从c到z的最长路径，那么 dist[z]=max(dist[ui]+w(ui,z))..

这里是一个省略了边集权重的3个前任的示例：

所以为了找到到z的最长路径，我们首先需要找到到其前任的最长路径，并在其值加上边权重后取最大值。

这要求我们每次访问一个顶点u时，必须已经分析和计算好了u的所有前任。

所以问题是: 对于任何顶点u，如何确保一旦设置了dist[u]，就不会再改变dist[u]呢? 换句话说: 如何确保在考虑从u发出的任何边之前，我们已经考虑了从c到u的所有路径？

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

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

- Xline

Answer 2

令f(u)为从c到u的最大利润。然后你想要计算f(z)。可以使用动态规划/拓扑排序在线性时间内轻松计算。

初始化除c以外每个u的f(u) = -无穷大，并且f(c) = 0。然后，在您的DAG上按某种拓扑顺序计算f的值。因此，由于该顺序是拓扑的，对于正在计算的节点的每个入边，已经计算了其他端点，因此只需选择此节点的最大可能值，即对于每个入边(v, u)，f(u) = max(f(v) + cost(v, u))。

- AlexAlvarez

Answer 3

最好使用拓扑排序而不是Bellman-Ford，因为它是DAG。

来源：http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

编辑：

G是一个带有负边的DAG。

一些边缩小了您的利润，而另一些增加了您的利润

• 边-增加利润-正值
• 边-减少利润-负值

在TS之后，对于TS顺序中的每个顶点U-松弛每个出边。

dist[] = {-INF, -INF, ….}
dist[c] = 0 // source

for every vertex u in topological order
  if (u == z) break; // dest vertex
  for every adjacent vertex v of u
    if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
      dist[v] = dist[u] + weight(u, v)

ans = dist[z];

- Mitesh Pathak

---

只有当你需要寻找最短路径时，这才是正确的。 - Xline

@MiteshPathak 我不是在寻找任意节点到任意节点的最长路径，而是在两个特定节点之间寻找最长路径。 - evenodd

如果是这种情况，在(v ==目标节点)之前的for循环中断。 - Mitesh Pathak

@evenodd 更新了我的答案。应该是 u == 目标节点。 - Mitesh Pathak

问题在于，如果它在到达目标节点时停止探索，可能没有探索到该目标节点的其他路径。 - evenodd