TOPICS
Search

Longest Path


The longest path problem asks to find a path of maximum length in a given graph. The problem is NP-complete, but there exists an efficient dynamic programming solution for acyclic digraphs.

The detour matrix is a real symmetric matrix whose (i,j)th entry is the length of the longest path from vertex i to vertex j.

For a traceable graph, longest paths correspond to Hamiltonian paths.

Finding a longest path is challenging for stacked book graphs and Apollonian networks.


See also

Antipodal Graph, Bellman-Ford Algorithm, Detour Index, Detour Matrix, Detour Polynomial, Graph Circumference, Hamiltonian Cycle, Hamiltonian Path, Path Polynomial, Shortest Path Problem, Traveling Salesman Problem

Explore with Wolfram|Alpha

References

Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

Cite this as:

Weisstein, Eric W. "Longest Path." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LongestPath.html

Subject classifications