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 th entry is the length of the longest
path from vertex
to vertex .
For a traceable graph, longest paths correspond
to Hamiltonian paths.
Finding a longest path is challenging for stacked
book graphs and Apollonian networks.
See alsoAntipodal Graph
, Bellman-Ford Algorithm
, Detour Index
, Detour Polynomial
, Hamiltonian Cycle
, Path Polynomial
, Traveling Salesman Problem
Explore with Wolfram|Alpha
ReferencesZamfirescu, 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