In un dag, trovando il percorso con il punteggio più alto

Question

Dato un grafico aciclico diretto in cui ogni nodo ha un punteggio intero assegnato, qual è un modo veloce per trovare il percorso da un vertice di inizio e fine con il punteggio cumulativo più alto?Pensavo a un approccio DFS in cui iniziamo alla fine e corriamo il grafico inverso, risparmiando a ciascun nodo il miglior punteggio cumulativo raggiungibile.Per stampare i risultati, iniziamo al primo nodo e scegli avidamente il nodo successivo con il punteggio cumulativo più alto.Tuttavia, non penso che questo sia il modo migliore perché potremmo attraversare gli stessi percorsi un sacco di volte se ci viene dato un grafico scortese.C'è un modo migliore di fare questo?

Answer 1

Suggerimento: trova un ordine topologico e per ogni vertice $ V $ , nell'ordine topologico, calcolo (il punteggio di) il percorso con il punteggio più alto cheTermina a $ V $ .