Dynamic Graph Programming

Error

In solutions using dynamic programming, the order in which the dynamics are calculated is important (it is necessary that the values ​​on which the current one depends are calculated before).
Therefore, if it is necessary to use dynamic programming on directed acyclic graphs, it is necessary to initially construct a topological sorting of the graph. Then calculate the dynamics by sorting through the vertices in the order of the constructed topological sort (depending on the problem, the traversal order can be either from sources to sinks or vice versa).
 
 

If the graph contains cycles (there is no topological sort), then two tricks can help:

1) Calculate the dynamics n times, where n is the number of vertices in the graph (by analogy with the Ford-Bellman algorithm). But this increases the asymptotics and is rarely efficient in general.

2) Construct graph condensation. For each strongly connected component of the original graph, solve the problem separately. The condensed graph is acyclic and for it you can use the standard approach with topological sorting, while using as vertex values, the calculated values ​​for the strongly connected components. This method is mainly used.