Encuentre la ruta más larga en un gráfico cíclico dirigido de una fuente S a un destino f. Suponga que no existe ciclos de peso positivos

Question

Tengo que encontrar la ruta más larga en un gráfico cíclico dirigido de una fuente a un destino f. Suponga que no existen ciclos de peso positivos a pesar de que no existen ciclos de peso positivos, existen ciclos de 0 o pesos negativos. ¿Alguien puede sugerir un algoritmo para encontrar el camino más largo en este caso? Por favor cita la fuente si es posible.

Gracias

Answer 1

No estoy seguro de si esto funcionará (necesita verificarlo) pero ... puede hacer algo similar a:

Dejar min = min weight on the graph.
max = max weight on the graph.
Establezca nuevos pesos para todos los bordes = wNew(e) = max - (wOld(e)-min).

Ahora hay wights negativos y los pesos están en orden inverso (lo que significa si w(e1) era más grande que w(e2) ahora es más pequeño).

¿Qué pasa si ahora buscamos la ruta más corta?

Answer 2

Simplemente niegue sus pesas de borde y ejecute un algoritmo de ruta más corto (por ejemplo, Bellman-Ford).

Los ciclos de peso cero podrían ser un problema. Deberá romper los lazos en sus caminos eligiendo el más corto (de longitud, no en peso). Una forma de hacerlo es hacer que sus pesos sean un par (-(peso original), 1), agregarlos por pares y hacer pedidos lexicográficos.

Ver también Camino más largo entre dos vértices

Answer 3

Si obtienes un DCG, puedes bucear para siempre antes de llegar a tu objetivo, ese sería el "camino más largo". En ese caso, la pregunta está incompleta, y el algoritmo probablemente se ve diferente según los detalles.

Esto suena como tarea.