Ruta acíclica más larga en un gráfico no ponderado dirigido

Question

¿Qué algoritmo se puede utilizar para encontrar la ruta más larga en un gráfico acíclico dirigido no ponderado?

Answer 1

Dynamic programming. También se hace referencia en Longest path problem, dado que es un DAG.

El siguiente código de Wikipedia:

algorithm dag-longest-path is 
    input: 
     Directed acyclic graph G 
    output: 
     Length of the longest path 

    length_to = array with |V(G)| elements of type int with default value 0 

    for each vertex v in topOrder(G) do 
     for each edge (v, w) in E(G) do 
      if length_to[w] <= length_to[v] + weight(G,(v,w)) then 
       length_to[w] = length_to[v] + weight(G, (v,w)) 

    return max(length_to[v] for v in V(G)) 

Answer 2

Mientras el grafo es acíclico, todo lo que tiene que hacer es negar los pesos de las aristas y ejecutar cualquier algoritmo de ruta más corta.

EDITAR: Obviamente, necesita un algoritmo de ruta más corta que admita contrapesos negativos. Además, el algoritmo de Wikipedia parece tener una mejor complejidad de tiempo, pero dejaré mi respuesta aquí para referencia.

Answer 3

Wikipedia tiene un algoritmo: http://en.wikipedia.org/wiki/Longest_path_problem

Parece que utilizan ponderaciones, pero debería funcionar con ponderaciones todo listo para

1.

Answer 4

puede ser resuelto por el método de la ruta crítica:
1. Encontrar un ordenamiento topológico
2. encuentre la ruta crítica
vea [Horowitz 1995], Fundamentos de las estructuras de datos en C++, Computer Science Press, Nueva York.

La estrategia codiciosa (por ejemplo, Dijkstra) no funcionará, sin importar: 1. use "max" en lugar de "min" 2. convierta los pesos positivos a negativos 3. dé un número muy grande M y use M-w como peso.