最长路径问题是在给定图中找到最大长度的简单路径的问题。 如果路径没有任何重复的顶点,则称为简单路径; 路径的长度可以通过其边数来测量,或者(在加权图中)通过其边缘的权重之和来测量。 与可以在没有负权重循环的图中的多项式时间中求解的最短路径问题相比,最长路径问题是NP难的,这意味着除非P = NP,否则它不能在任意图的多项式时间内求解。 还已知更强的硬度结果,表明难以近似。 然而,它具有有向无环图的线性时间解,它在寻找调度问题的关键路径方面具有重要的应用。可以使用哈密顿路径问题的减少来显示未加权最长路径问题的NP-hard:当且仅当其最长路径具有长度n-1时,图G具有哈密顿路径,其中n是顶点的数量。 G.由于哈密顿路径问题是NP完全的,这种减少表明最长路径问题的决策版本也是NP完全的。在该决策问题中,输入是图G和数k;如果G包含k个或更多边的路径,则所需的输出为“是”,否则为无。