Problema del camí més llarg

En teoria de grafs i ciència computacional teòrica, el problema del camí més llarg és el problema de trobar un camí simple de màxima longitud possible en un determinat graf. Un camí s'anomena simple si no té cap vèrtex repetit; la longitud d'un camí es pot mesurar pel seu nombre d'arestes, o (en grafs ponderats) per la suma dels pesos de les seves arestes.

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, la qual cosa 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 ordenament topològic. També es pot solucionar en un graf dirigit acíclic invertint els pesos i utilitzant l'algorisme de Bellman-Ford (aquest enfocament no funciona en general perquè crea cicles de pes negatiu).