Programación de gráficos dinámicos

Error

En las soluciones que utilizan programación dinámica es importante el orden en que se calculan las dinámicas (es necesario que antes se calculen los valores de los que depende la actual).
Por lo tanto, si es necesario utilizar programación dinámica en grafos acíclicos dirigidos, es necesario construir inicialmente una ordenación topológica del grafo. Luego, calcule la dinámica clasificando los vértices en el orden de la clasificación topológica construida (según el problema, el orden transversal puede ser de fuentes a sumideros o viceversa).
 
 

Si el gráfico contiene ciclos (no hay clasificación topológica), dos trucos pueden ayudar:

1) Calcular la dinámica n veces, donde n es el número de vértices del gráfico (por analogía con el algoritmo de Ford-Bellman). Pero esto aumenta los asintóticos y rara vez es eficiente en general.

2) Construir el gráfico de condensación. Para cada componente fuertemente conectado del gráfico original, resuelve el problema por separado. El gráfico condensado es acíclico y para ello puede utilizar el enfoque estándar con clasificación topológica, mientras utiliza como valores de vértice, los valores calculados para los componentes fuertemente conectados. Este método se utiliza principalmente.