algorithm - keywords - meta tags seo 2018

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

Question

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

Answer 1

Mientras el gráfico sea acíclico, todo lo que necesita hacer es negar los pesos de los bordes y ejecutar cualquier algoritmo de ruta más corta.

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

Answer 2

Se puede resolver mediante el método de ruta crítica:
1. encontrar un ordenamiento topológico
2. encontrar el camino crítico
ver [Horowitz 1995], Fundamentals of Data Structures 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 Mw como peso.

Answer 3

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

Parece que usan ponderaciones, pero deberían funcionar con ponderaciones establecidas en 1.

Answer 4

Programación dinámica . También se hace referencia en el problema Ruta más larga , 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))