Programmation graphique dynamique

Error

Dans les solutions utilisant la programmation dynamique, l'ordre dans lequel les dynamiques sont calculées est important (il faut que les valeurs dont dépend celle en cours soient calculées avant).
Donc, s'il est nécessaire d'utiliser la programmation dynamique sur des graphes acycliques orientés, il faut d'abord construire un tri topologique du graphe. Calculez ensuite la dynamique en triant les sommets dans l'ordre du tri topologique construit (selon le problème, l'ordre de parcours peut aller des sources aux puits ou vice versa).
 
 

Si le graphe contient des cycles (il n'y a pas de tri topologique), alors deux astuces peuvent aider :

1) Calculer la dynamique n fois, où n est le nombre de sommets du graphe (par analogie avec l'algorithme de Ford-Bellman). Mais cela augmente les asymptotiques et est rarement efficace en général.

2) Construire une condensation de graphes. Pour chaque composante fortement connexe du graphe original, résolvez le problème séparément. Le graphe condensé est acyclique et pour cela vous pouvez utiliser l'approche standard avec tri topologique, tout en utilisant comme valeurs de sommet, les valeurs calculées pour les composants fortement connectés. Cette méthode est principalement utilisée.