最长路径问题

在给定图中寻找最大长度的简单路径的任务在图论和理论计算机科学中称为最长路径问题。 如果一条路径不多次包含一个节点，则称为简单路径。 路径的长度可以通过两种方式测量：通过边的数量或通过其边的权重之和。

与可以在多项式时间内解决的最短路径问题相比，最长路径问题属于 NP-hard 问题组。 这意味着它不能在多项式时间内求解，除非 P=NP。 可以看出，近似也很困难，但是，对于有向非循环图，可以使用拓扑排序在线性时间内解决问题。 一个重要的应用领域是寻找规划任务中的关键路径。

可以使用哈密顿路径问题显示未加权最长路径的 NP 硬度。 图 G  只有当其最长路径长度为 n − 1 时才有哈密顿路径，其中 n 是 G 中的顶点数是. 由于哈密顿路径问题是 NP 完全问题，最长路径的决策版本也是 NP 完全问题。在决策版本中，输入由图 G 和数字 k 组成。 如果 G 包含一条带有 k 或更多边的简单路径，则输出为“是”。

如果最长路径问题可以在多项式时间内解决，那么决策版本可以通过比较最长路径的长度与 k 来解决。因此，最长路径问题是NP-hard。 “给定图中是否存在至少有 k 条边的路径”这个问题是 NP 完全问题。

在带权完全图中，带权最长路径问题等同于旅行商问题，因为最长路径必然包含所有节点。