Dijkstra para la ruta más larga en un DAG

Question

Estoy tratando de averiguar si es posible usar el algoritmo de Dijkstra para encontrar la ruta más larga en una ruta acíclica dirigida. Sé que no es posible encontrar el camino más largo con Dijkstra en un gráfico general, debido a los ciclos de costos negativos. Pero debería funcionar en un DAG, creo. A través de Google encontré muchas fuentes conflictivas. Algunos dicen que funciona en un dag y algunos dicen que no funciona, pero no encontré una prueba o un ejemplo de contador. ¿Puede alguien señalarme una prueba o un contraejemplo?

Answer 1

Pensé en el problema y creo que no es posible en general. Ser acíclico no es suficiente, creo.

Por ejemplo:

queremos ir de A a C en este dag.

a - > b - > c 
|   /\ 
v   | 
d - - - - - 

DC tiene una longitud de 4

anuncio tiene longitud 1

todos los demás tienen longitud 2

Si acaba de cambiar la función min con una función max, el algoritmo dará lugar a ABC pero el camino más largo es adc.

He encontrado dos casos especiales en los que se pueden utilizar Dijkstra para calcular el camino más largo:

1. El gráfico no sólo está dirigido acíclico, sino también acíclico si se quita las direcciones. En otras palabras: es un árbol. Porque en un árbol el camino más largo es también el más corto.
2. El gráfico tiene solo pesos negativos. Luego puede usar max en lugar de min para encontrar la ruta más larga. PERO esto funciona solo si los pesos son realmente negativos. Si solo inviertes pesas positivas, no funcionará.

Answer 2

El único requisito es no tener ciclos negativos. Si no tiene los ciclos, puede reasignar los negativos agregando el valor absoluto más alto de los pesos negativos a todos los pesos. De esa forma perderás los wights negativos, ya que todo el peso será igual o mayor que cero. Entonces, también, resumir, lo único de lo que preocuparse es no tener un ciclo negativo.

Answer 3

No tenemos tres formas posibles de aplicar Dijkstra, ninguno de ellos funcionará:
utilizan 1.Directly operaciones de “max” en lugar de las operaciones “min”.
2. Convierta todos los pesos positivos en negativos. Luego encuentra el camino más corto.
3.Deje un número positivo muy grande M. Si el peso de un borde es w, ahora M-w se usa para reemplazar a w. Luego encuentra el camino más corto.

Para DAG, el método de ruta crítica funcionará:
1: busque un orden topológico.
2: Encuentre la ruta crítica.
ver [Horowitz 1995] E. Howowitz, S. y D. Sahni Metha, Fundamentos de Estructuras de datos en C++, Computer Science Press, Nueva York, 1995

Answer 4

que sugieren modificar el algoritmo de Dijkstra para tomar la invertida valor del peso del borde. Debido a que el gráfico es acíclico, el algoritmo no ingresará un bucle sin fin, utilizando los pesos negativos para seguir optimizando.Lo que es más, ahora positivos pesos se vuelven negativos, pero, de nuevo, no hay ciclos. Esto funcionará incluso si el gráfico es no dirigido, siempre que no permita la reinserción de los nodos visitados (es decir, detenga el salto interminable entre dos nodos, porque agregar valor negativo siempre será mejor).

Answer 5

problema de la distancia más larga no tiene subestructura óptima para cualquier gráfico, DAG o no. Sin embargo, cualquier problema de distancia más larga en el gráfico G es equivalente a un problema de distancia más corta en un gráfico transformado G '= - G, es decir, el signo de cada peso del borde se invierte.

Si se espera que el gráfico transformado G 'tenga bordes y ciclos negativos, entonces el algoritmo Bellman-Ford se usa para encontrar la distancia más corta. Sin embargo, si se garantiza que G solo tiene pesos no negativos (es decir, G 'es pesos no positivos), entonces el algoritmo de Dijkstra podría ser una mejor opción que Bellman-Ford. (ver la respuesta de 'Evgeny Kluev' para graph - Dijkstra for The Single-Source Longest Path) Si el G es un DAG, entonces G 'también será un DAG. Para DAG, tenemos un mejor algoritmo para encontrar la distancia más corta y debería elegirse sobre el de Dijkstra o el de Bellman-Ford.

Resumen:
más larga problema del camino no tiene subestructura óptima y modificando así la función min-peso en el algoritmo de Dijkstra para la función max-peso por sí sola no funcionará para una gráfica, ya sea DAG o no. En lugar de modificar cualquier ruta más corta-algoritmo (así de una manera trivial), más bien nosotros transformamos el G y ve quienes más corto algoritmo de ruta funciona mejor en el G. transformado

Nota

 A-------B 
    |  |    assume: edges A-B, B-C, C-A of same weight 
    |  | 
    +-------C 

Vemos MAX_DIS (a, B) = A-> C-> B
Por "MAX_DIS" ser estructura óptima, en el caso anterior, la relación

MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied. 

Pero no es como vemos, MAX_DIS (A, C) = A-> B-> C y MAX_DIS (C, B) = C-> A-> B y por lo tanto proporciona un ejemplo de que el problema de distancia más larga puede no tener una subestructura óptima