Programação de gráficos dinâmicos

Error

Em soluções que usam programação dinâmica, a ordem em que as dinâmicas são calculadas é importante (é necessário que os valores dos quais a corrente depende sejam calculados antes).
Portanto, se for necessário usar programação dinâmica em grafos acíclicos direcionados, é necessário construir inicialmente uma ordenação topológica do grafo. Em seguida, calcule a dinâmica classificando os vértices na ordem da classificação topológica construída (dependendo do problema, a ordem de passagem pode ser de fontes para sumidouros ou vice-versa).
 
 

Se o gráfico contiver ciclos (não há classificação topológica), dois truques podem ajudar:

1) Calcule a dinâmica n vezes, onde n é o número de vértices do grafo (por analogia com o algoritmo de Ford-Bellman). Mas isso aumenta os assintóticos e raramente é eficiente em geral.

2) Construa a condensação do grafo. Para cada componente fortemente conectada do grafo original, resolva o problema separadamente. O gráfico condensado é acíclico e para isso você pode usar a abordagem padrão com classificação topológica, enquanto usa como valores de vértice, os valores calculados para os componentes fortemente conectados. Este método é usado principalmente.