Problema del camí més llarc

En teoria de grafos, el problema del camí més llarc és, donat un grafo, trobar un camí simple de llongitut màxima. A diferència del problema del camí més curt, que es pot solucionar en temps polinòmic en grafos sense cicles negatius, este problema és NP-complet, lo que vol dir que la solució òptima no es pot trobar en temps polinòmic a menos que P=NP.

El problema del camí més llarc té una solució de programació dinàmica eficient en un grafo dirigit acíclic utilisant ordenament topològic. També es pot solucionar en un grafo dirigit acíclic invertint els pesos i utilisant l'algoritme de Bellman-Ford(este enfocament no funciona en general perque crea cicles de pes negatiu).