动态图编程

Error

在使用动态规划的解决方案中，动态计算的顺序很重要（必须先计算当前值所依赖的值）。
因此，如果需要在有向无环图上使用动态规划，就需要先构造一个图的拓扑排序。然后通过按照构建的拓扑排序的顺序对顶点进行排序来计算动态（根据问题，遍历顺序可以是从源到汇，也可以是从源到汇）。
 
 

如果图中包含循环（没有拓扑排序），那么两个技巧可以提供帮助：

1）计算n次动态，其中n是图中的顶点数（类推Ford-Bellman算法）。但这增加了渐近性，一般情况下效率很低。

2) 构造图形凝聚。对于原始图的每个强连通分量，分别求解问题。压缩图是非循环的，您可以使用拓扑排序的标准方法，同时使用强连通分量的计算值作为顶点值。主要采用这种方法。