En un DAG, encontrar el camino con la puntuación más alta.

Question

Dado un gráfico acíclico dirigido en el que cada nodo tiene un puntaje entero asignado, ¿qué es una forma rápida de encontrar la ruta de un vértice de inicio y extremo con la puntuación acumulativa más alta?Pensé en un enfoque DFS en el que comenzamos al final y ejecutamos la gráfica de la manera inversa, ahorrando en cada nodo la mejor puntuación acumulativa alcanzable.Para imprimir los resultados, comenzamos en el primer nodo y seleccione con avidez el siguiente nodo con la puntuación acumulativa más alta.Sin embargo, no creo que esta sea la mejor manera, ya que podríamos atravesar los mismos caminos muchas veces si nos damos un gráfico hostil.¿Hay una mejor manera de hacer esto?

Answer 1

Sugerencia: Encuentre un pedido topológico, y para cada vértice $ v $ , en el orden topológico, cómputo (la puntuación de) la ruta con la puntuación más alta quetermina en $ v $ .