Si hallas algún fallo en tu código o proyecto, recuerda probar siempre en un ambiente de testing antes añadir el código al trabajo final.
Solución:
El problema de la distancia más larga no tiene una subestructura óptima por cualquier gráfico, DAG o no. Sin embargo, cualquier problema de la distancia más larga en el gráfico G es equivalente a un problema de la distancia más corta en un gráfico transformado G’=-G, es decir, se invierte el signo del peso de cada borde.
Si se espera que el gráfico transformado G’ tenga aristas y ciclos negativos, entonces se utiliza el algoritmo de Bellman-Ford para encontrar la distancia más corta. Sin embargo, si se garantiza que G solo tiene pesos no negativos (es decir, G’ tiene pesos no positivos), entonces el algoritmo de Dijkstra podría ser una mejor opción que Bellman-Ford. (consulte la respuesta de ‘Evgeny Kluev’ para el gráfico – Dijkstra para la ruta más larga de fuente única) Si 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:
El problema de la ruta más larga no tiene una subestructura óptima y, por lo tanto, la modificación de la función de peso mínimo en el algoritmo de Dijkstra a la función de peso máximo por sí sola no funcionará para un gráfico, ya sea DAG o no. En lugar de modificar cualquier algoritmo de ruta más corta (bueno, de una manera trivial), preferimos transformar la G y ver qué algoritmo de ruta más corta funciona mejor en la G transformada.
Nota
A-------B
| | assume: edges A-B, B-C, C-A of same weight
| |
+-------C
Vemos MAX_DIS(A,B)= A->C->B
Para que “MAX_DIS” sea una 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 la distancia más larga puede no tener subestructura óptima.
Pensé en el problema y creo que no es posible en general. Creo que ser acíclico no es suficiente.
Por ejemplo:
Queremos ir de a a c en este día.
a - > b - > c
| /
v |
d - - - - -
dc tiene longitud 4
el anuncio tiene una longitud de 1
todos los demás tienen longitud 2
Si simplemente reemplaza la función min con una función max, el algoritmo conducirá a abc pero la ruta más larga es adc.
Encontré dos casos especiales en los que puedes usar Dijkstra para calcular la ruta más larga:
- El gráfico no solo está dirigido acíclico, sino también acíclico si elimina las direcciones. En otras palabras: es un árbol. Porque en un árbol el camino más largo es también el camino más corto.
- El gráfico solo tiene 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 invierte pesos positivos, no funcionará.
Te mostramos comentarios y valoraciones
Recuerda algo, que puedes decir si te fue preciso.