DAG（有向无环图）最长路 信托行为的起点和终点分别是什么

文章目录 1 问题描述1.1 求整个DAG的最长路径（即不固定起点和终点）1.2 固定终点，求DAG的最长路径 2 求解问题12.1 求解最长路径长度2.2 求解最长路径2.2.1 路径序列的字典序 3 求解问题23.1 求解最长路径长度 3 应用3.1 实际例题

1 问题描述 1.1 求整个DAG的最长路径（即不固定起点和终点） 1.2 固定终点，求DAG的最长路径 2 求解问题1 2.1 求解最长路径长度

给定一个有向无环图，怎么求解整个图所有路径中权值之和最大的那条。

如下图所示：

B->D->F->I就该图的最长路径，长度为9。

令dp[i]表示从i号顶点出发能获得的最长路径长度，这样所有dp[i]中的最大值就是整个DAG的最长路径。

求解dp数组， 如果从i号顶点出发能到达顶点有 就j1,j2,…jk,而dp[j1],dp[j2],…dp[jk]均已知，那么就有 d p [ i ] = m a x { d p [ j ] + l e n g h t [ i ⟶ j ] ｜ ( i , j ∈ E ) } dp[i] = max{dp[j] + lenght[i longrightarrow j] ｜(i,jin E)} dp[i]=max{dp[j]+lenght[i⟶j]｜(i,j∈E)}

如上图所示，需要逆拓扑序列求解dp数组，用递归求解（以邻接矩阵为例）：

int DP(int i){ if(dp[i] > 0) return dp[i];//dp[i]已计算完毕 for (int j = 0; j dp[i] = max(dp[i], DP(j)+G[i][j]); } } return dp[i];//返回计算完毕的dp[i]}

从出度为0的顶点出发的最长路径长度为0，因此边界为这些顶点的dp值为0。 但具体实现，可以对整个数组dp初始化为0，这样dp函数当前访问的顶点i的出度为0时，就会返回dp[i]= 0(以此为dp的边界)，而出度不为0的顶点则会递归求解，递归过程中遇到已经计算过的顶点，则会直接返回对应的dp值。

2.2 求解最长路径

可以开一个int型数组choice来记录最长路径上顶点的后继顶点。【如果存在多条最长路径，把choice数组改为vector数组】

实现代码如下：

int DP(int i){ if(dp[i] > 0) return dp[i];//dp[i]已计算完毕 for (int j = 0; j int temp = DP(j) + G[i][j];//单独计算，防止if调用DP函数两次 if(temp > dp[i]){ dp[i] = temp; choice[i] = j; } } } return dp[i];//返回计算完毕的dp[i]}//调用前，要先求出最大的dp[i],然后将i作为路径起点传人void printPath(int i){ printf("%d ", i); while(choice[i] != -1){//choice初始化为-1 i = choice[i]; printf("->%d ", i); }} 记录每次决策所选择的策略，然后在dp数组计算完毕之后，根据具体情况进行递归或迭代来获取方案。 2.2.1 路径序列的字典序

模仿字符串来定义路径字典序： 如有两个路径 a1 ⟶ longrightarrow ⟶a2 ⟶ longrightarrow ⟶… ⟶ longrightarrow ⟶am与把b1 ⟶ longrightarrow ⟶b2 ⟶ longrightarrow ⟶… ⟶ longrightarrow ⟶bn，且a1=b1,a2= b2,……，ak = bk,ak+1 if(G[i][j] != INF){ dp[i] = max(dp[i], Dp(j) + G[i][j]); } } return Dp[i];}

如果用dp[i]表示以i号结尾能获得的最长路径长度，那么dp[T]就是结果。

3 应用 1 求关键路径2 如经典的矩形嵌套问题

矩形嵌套问题：给出n个矩形的长和宽，定义矩形的嵌套关系为：如果有两个矩形A和矩形B，其中矩形A的长和宽分别为a、b，矩形B的长和宽分别为c、d，且满足a if(G[i][j] != 0){ int temp = Dp(j) + G[i][j]; if(temp > dp[i]){ dp[i] = temp; } } } return dp[i];}int main(int argc, char const *argv[]){ int N; scanf("%d", &N); while(N--){ memset(G, 0, sizeof(G));//初始化 fill(dp, dp + MAXN, 0); scanf("%d", &n); int a = 0, b = 0, maxIndex; for (int i = 0; i //长的边靠前 swap(edge[i][0], edge[i][1]); } if(edge[i][0] > a && edge[i][1] > b){//求最大的矩形，即源点 a = edge[i][0]; b = edge[i][1]; maxIndex = i; } for (int j = 0; j //矩形i能嵌套矩形j G[i][j] = 1; }else if(edge[i][0]