为什么这个算法找不到有向无环图中的最长路径？

Question

我试过用动态规划来解决这道题。 dp[i] 存储以 i 结尾的最长路径。对于从 x 到 y 的每条边，我将 dp[y] 更新为 dp[y] 和 dp[x+1] 之间的最大值。

它适用于输入输出示例，但在判断时未通过某些测试用例。还没有想出一个测试用例，fails.Any 将不胜感激。

N 是顶点数
M 是边数
x y 表示从 x 到 y 的边
输出应该是图中最长路径的长度。

示例输入
N M
x1 y1
x2 y2
x3 y3
.
.
.
输入 1
4 5
1 2
1 3
3 2
2 4
3 4
输出 1
3
输入 2
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
输出 2
3

#include <bits/stdc++.h>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin>>n>>m;

    vector<int> dp(n+1,0);
    //dp[i] denotes max length of path ending at node i
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        dp[y]=max(dp[x]+1,dp[y]);
    }
    int ans=0;
    // for(int i=0;i<n+1;i++)
    //  cout<<i<< " : "<<dp[i]<<endl;
    for(int i=0;i<n+1;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
}

Answer 1

这里的问题是，虽然你确实会处理每条边，但你处理它们的顺序并不能保证你会真正发现你想要的路径。例如，考虑这个 DAG：

1 -> 2 -> 3

假设输入文件的边顺序如下：

2 3
1 2

最初，dp[1]、dp[2] 和 dp[3] 均为零。在看到第一行 dp[2] 设置为 1 之后，在第二行之后 dp[1] 也设置为 1。然而，这些最终值是不正确的，因为 dp[2] 应该是 2.

失败的原因是您正在查看的 DP 解决方案仅在您访问拓扑顺序中的边时才有效，在这种情况下，每次您看到从 x 到 y 的边时，您就知道您已经在考虑更新 y 之前计算到 x 的最长路径的长度。

要解决此问题，请存储您读入的边并按节点的拓扑顺序访问边。您可以通过多种方式找到拓扑排序，我会把细节留给您。 :-)

希望对您有所帮助！

为什么这个算法找不到有向无环图中的最长路径？

Why doesn't this algorithm find the longest path in a directed acyclic graph?

c++

algorithm

graph

directed-acyclic-graphs