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 .