Dans un Dag, trouver le chemin avec le score le plus élevé

Question

Étant donné un graphique acyclique dirigé dans lequel chaque nœud dispose d'un score entier assigné, quel est un moyen rapide de trouver le chemin d'un sommet de début et de fin avec le score cumulatif le plus élevé?J'ai pensé à une approche DFS dans laquelle nous commençons à la fin et à exécuter le graphique de la manière inverse, économisant à chaque noeud le meilleur score cumulatif réalisable.Pour imprimer les résultats, nous commençons au premier nœud et choisissez gourmandeusement le nœud suivant avec le score cumulatif le plus élevé.Cependant, je ne pense pas que c'est la meilleure façon possible, car nous pourrions parcourir les mêmes chemins si nous recevons un graphique hostile.Y a-t-il une meilleure façon de faire cela?

Answer 1

indice: trouvez un ordre topologique et pour chaque sommet $ V $ , dans la commande topologique, calculez (le score de) le chemin avec le score le plus élevé quese termine à $ v $ .