有序图中最长的路径

设G =（V，E）为有节点v_1，v_2，...，v_n的有向图。如果G具有以下属性，我们说G是一个有序图。有序图中最长的路径

每条边都从具有较低索引的节点进入具有较高索引的节点。也就是说，每个有向边都具有（v_i，v_j）的形式。
除v_n之外的每个节点都至少有一条边离开它。也就是说，对于每个节点v_i，至少有一个形式边（v_i，v_j）。

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

如果你想看到漂亮的乳胶版本：here

我尝试：

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

有没有更好的方法来做到这一点？我认为，即使记忆我的算法仍然是指数。（这是从我在网上找到的一份旧期中期评论中得到的）

来源

2014-11-06 user2079802

你的做法是正确的，你将不得不做

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多项式作的Σ，并且因此将导致O(n^3)时间复杂度的方式的数量。

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

来源

2014-11-07 03:26:29

由于第一个属性，这个问题可以用O（E）来解决O（V^2）甚至更好，其中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];

}

来源

2014-11-07 03:14:40

有序图中最长的路径

回答

相关问题