Programmazione di grafici dinamici

Error

Nelle soluzioni che utilizzano la programmazione dinamica è importante l'ordine in cui vengono calcolate le dinamiche (è necessario che vengano calcolati prima i valori da cui dipende quella corrente).
Pertanto, se è necessario utilizzare la programmazione dinamica su grafi aciclici orientati, è necessario costruire inizialmente un ordinamento topologico del grafo. Quindi calcola la dinamica ordinando i vertici nell'ordine dell'ordinamento topologico costruito (a seconda del problema, l'ordine di attraversamento può essere dalle sorgenti ai sink o viceversa).
 
 

Se il grafico contiene cicli (non esiste un ordinamento topologico), allora due trucchi possono aiutare:

1) Calcolare la dinamica n volte, dove n è il numero di vertici nel grafico (per analogia con l'algoritmo di Ford-Bellman). Ma questo aumenta gli asintotici ed è raramente efficiente in generale.

2) Costruire la condensazione del grafo. Per ogni componente fortemente connessa del grafo originale, risolvi il problema separatamente. Il grafo condensato è aciclico e per esso si può utilizzare l'approccio standard con ordinamento topologico, utilizzando come valori di vertice i valori calcolati per le componenti fortemente connesse. Questo metodo è principalmente utilizzato.