In einem DAG finden Sie den Weg mit der höchsten Punktzahl

Question

Angesichts eines gerichteten, azyklischen Diagramms, in dem jeder Knoten eine zugewiesene Integer-Score hat, was ist eine schnelle Art, den Pfad von einem Start- und Ende-Scheitelpunkt mit der höchsten kumulativen Punktzahl zu finden?Ich dachte an einen DFS-Ansatz, in dem wir am Ende beginnen und den Grafik umgekehrt ausführen und an jedem Knoten speichern, der an jedem Knoten die beste kumulierte Punktzahl erreichbar ist.Um die Ergebnisse zu drucken, starten wir am ersten Knoten und wählen gierig den nächsten Knoten mit der höchsten kumulierten Punktzahl aus.Ich glaube jedoch nicht, dass dies der beste Weg ist, da wir möglicherweise die gleichen Wege viel Zeiten durchqueren, wenn wir ein unfreundliches Diagramm erhalten.Gibt es eine bessere Art, dies zu tun?

Answer 1

TIPP: Finden Sie eine topologische Reihenfolge und für jeden Vertex $ V $ , berechnen Sie in der topologischen Reihenfolge (die Punktzahl von) den Weg mit der höchsten Punktzahlendet bei $ V $ .