|
Problema del camino más largoEn teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP. El problema del camino más largo tiene una solución de programación dinámica eficiente en un grafo dirigido acíclico utilizando ordenamiento topológico. También se puede solucionar en un grafo dirigido acíclico invirtiendo los pesos y utilizando el algoritmo de Bellman-Ford(este enfoque no funciona en general porque crea ciclos de peso negativo).
|
