Em um DAG, encontrando o caminho com a maior pontuação

Question

Dado um gráfico acíclico direcionado no qual cada nó possui uma pontuação inteira atribuída, qual é uma maneira rápida de encontrar o caminho de um vértice de início e final com a maior pontuação acumulada?Pensei em uma abordagem DFS em que começamos no final e corremos o gráfico na maneira inversa, economizando em cada nó a melhor pontuação acumulada atingível.Para imprimir os resultados, começamos no primeiro nó e avidamente escolheu o próximo nó com a maior pontuação acumulada.No entanto, eu não acho que esta é a melhor maneira que poderíamos envolver os mesmos caminhos muitas vezes se tivermos um gráfico hostil.Existe uma maneira melhor de fazer isso?

Answer 1

Dica: Encontre uma encomenda topológica, e para cada vértice $ v $ , no pedido topológico, compute (a pontuação de) o caminho com a maior pontuação quetermina em $ v $ .