Longest Path Problem
# Longest Path Problem
It is the problem of finding a simple path of maximum length in a given graph.
Simple path: if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.
In contrast to the Shortest Path Problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is and the decision version of the problem, which asks whether a path exists of at least some given length, is .