本文主要是介绍DAG最长路问题详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DAG就是有向无环图，求解最长路，也就是所谓的关键路径。但是求解关键路径的方式比较复杂，而DAG上的最长路或者最短路问题又比较重要，很多问题都可以转换为求解DAG上的最长路或最短路问题。由于最长路和最短路的思想是一致的，因此下面以最长路为例：
主要分为两个问题：
（1）求整个DAG中的最长路径（即不固定起点和终点）
（2）固定终点，求DAG的最长路径
先解决第一个问题，给定一个有向无环图，怎样求解整个图的所有路径中权值之和最大的那条。
针对这个问题，令dp[i]表示从i号顶点出发能获得的最长路径长度，这样所有dp[i]的最大值就是整个DAG的最长路径长度。
求解dp数组时注意到dp[i]表示从i号顶点出发能获得的最长路径长度，这个除了使用逆拓扑排序来做，可以使用递归的方法。
int dp(int i){if(dp[i]>0){return dp[i];}for(int j=0;j<n;j++){if(G[i][j]!=INF){dp[i]=max(dp[i],dp(j)+G[i][j]);}}return dp[i];
}由于从出度为0的顶点出发的最长路径长度为0，因此边界为这些顶点的dp值为0，但具体实现中不妨对整个dp数组初始化为0，这样dp函数当前访问的顶点i的出度为0时就会返回dp[i]=0（以此作为dp的边界），而出度不是0的顶点则会递归求解，递归过程中遇到已经计算过的顶点则直接返回对应的dp值，于是从程序逻辑上按照了拓扑排序的顺序进行。
如何知道最长路径是那条？
事实上可以仿照Dijkstra算法中求解最短路径的做法。开一个int型choice数组记录最长路径上顶点的后继顶点，这样就可以像Dijkstra算法中那样来求解最长路径了，只不过由于choice数组存放的是后继顶点，因此使用迭代即可。如果最终可能有多条最长路径，将choice数组改为vector类型的数组即可。
int dp(int i){if(dp[i]>0){return dp[i];}for(int j=0;j<n;j++){if(G[i][j]!=INF){int temp=dp(j)+G[i][j];if(temp>dp[i]){dp[i]=temp;choice[i]=j;//i号顶点的后继顶点是j }}}return dp[i];
}
void printPath(int i){printf("%d",i);while(choice[i]!=-1){i=choice;printf("->%d",i);}
}对一般的动态规划问题而言，如果需要得到具体的最优方案，可以采用类似的方法，即记录每次决策所选择的策略，然后在dp数组计算完毕后根据具体情况进行递归或者迭代来获取方案。
求解最优方案时由于字典序的大小总是先根据序列中较前的部分来判断，因此序列中越靠前的顶点，其dp值应当越后计算（对一般的序列型动态规划问题也是如此）。
在上面讨论的问题上，接下来谈论第二个问题：固定终点，求DAG的最长路径长度。
此时假设规定的终点为T，那么可以令dp[i]表示从i号顶点出发到达终点T能获得的最长路径长度。
这个问题和上面问题的区别是边界，在第一个问题中没有固定终点，因此所有出度为0的顶点的dp值为0是边界；但是这个问题固定了终点，因此边界应该为dp[T]=0。而初始化时dp数组不能初始化为0，因为从某些顶点出发可能无法到达终点T。合适的做法是初始化dp数组为一个负的大数，来保证无法到达终点的含义得以表达；然后设置一个vis数组表示顶点是否已经被计算。
int dp(int i){if(vis[i]){return dp[i];}vis[i]=true;for(int j=0;j<n;j++){if(G[i][j]!=INF){dp[i]=max(dp[i],dp(j)+G[i][j]);}}return dp[i];
}记录方案及如何选择字典序最小的方案均与第一个问题相同。
这篇关于DAG最长路问题详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
