有序图中的最长路径

Question

令 G = (V, E) 为节点 v_1, v_2,..., v_n 的有向图。如果 G 具有以下性质，则称 G 是有序图。

• 每条边从索引较低的节点到索引较高的节点。也就是说，每条有向边都具有 i < j 的形式 (v_i, v_j)。
• 除了 v_n 之外的每个节点都有至少一条边离开它。也就是说，对于每个节点 v_i，至少有一条 (v_i, v_j) 形式的边。

给出一个有效的算法，该算法采用有序图 G 并返回从 v_1 开始到 v_n 结束的最长路径的长度。

如果你想看到漂亮的乳胶版本：在这里

我的尝试：

动态规划。Opt(i) = max {Opt(j)} + 1. 对于所有 j 这样的 j 可以从 i 到达。

也许有更好的方法来做到这一点？我认为即使有记忆，我的算法仍然是指数级的。（这只是我在网上找到的旧中期审查）

Answer 1

你的方法是对的，你将不得不做

Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i

但是，只有在没有记忆的情况下运行它时，这才是指数级的。通过记忆化，当您在节点 i 上时，您将获得每个节点 j 的记忆化最优值，j > i。

对于最坏情况的复杂性，让我们假设可以连接的每两个节点都是连接的。这意味着，v_1与(v_2, v_3, ... v_n); v_i与 相连(v_(i+1), v_(i+2), ... v_n)。

顶点数 ( V) = n

因此，边数 ( E) =n*(n+1)/2 = O(V^2)

让我们把注意力集中在一个顶点上v_k。对于这个顶点，我们必须遍历已经导出的(n-k)节点的最优值。

v_k直接到达方式数= (k-1)

因此，最坏情况下的时间复杂度 => sigma((k-1)*(n-k)) from k=1 to k=n，它是 2 次幂多项式的 sigma，因此将导致O(n^3)时间复杂度。

简单地说，最坏情况的时间复杂度是O(n^3) == O(V^3) == O(E) * O(V) == O(EV)。

Answer 2

由于第一个属性，这个问题可以用 O(V^2) 解决，甚至可以用 O(E) 解决，其中 V 是顶点数，E 是边数。事实上，它使用动态编程方法，与您提供的方法非常相似。令 opt[i] 为 v_1 到 v_i 的最长路径的长度。然后

opt[i] = max(opt[j]) + 1 where j < i and we v_i and v_j is connected, 
                         using this equation, it can be solved in O(V^2). 

更好的是，我们可以用另一种顺序来解决这个问题。

int LongestPath() {
   for (int v = 1; v <= V; ++v) opt[v] = -1;
   opt[1] = 0;
   for (int v = 1; v <= V; ++v) {
     if (opt[v] >= 0) {
     /* Each edge can be visited at most once,
        thus the runtime time is bounded by |E|.
      */ 
      for_each( v' can be reached from v) 
         opt[v'] = max(opt[v]+1, opt[v']);
    }
  }
 return opt[V];

}