A longest path of a graph is a graph path having maximum length. A longest path that contains every graph vertex is a Hamiltonian path, and a graph containing such a path is called a traceable graph. In a traceable graph, every longest path is a Hamiltonian 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 
th entry is the length of the longest
path from vertex 
to vertex 
.
Finding a longest path is challenging for stacked book graphs and Apollonian networks.
