Problema del camí més llarg

De Viquipèdia
Dreceres ràpides: navegació, cerca

Dins la teoria de grafs, el problema del camí més llarg és, donat un graf, trobar un camí simple de longitud màxima. A diferència del problema del camí més curt, que es pot solucionar en temps polinòmic en grafs sense cicles negatius, aquest problema és NP-complet, el que vol dir que la solució òptima no es pot trobar a temps polinòmic a menys que P = NP.

El problema del camí més llarg té una solució de programació dinàmica eficient en un graf dirigit acíclic utilitzant selecció topològica. També es pot solucionar en un graf dirigit acíclic invertint els pesos i utilitzant el algorisme de Bellman-Ford (aquest enfocament no funciona en general perquè crea cicles de pes negatiu).