最长路径问题 在图论和理论计算机科学中最长路径问题是指在给定的图中找出长度最长的简单路径一条不具有任何重复顶点的路径被称为简单路径无权图中路径的长度就是边的数量而有权图中路径长度是边权重之和不同的是与此相反的最短路径问题不含负权环可以在多项式时间内解决而最长路径问题是NP困难的这意味着除非P  NP否则对应于任意的图没有办法在多项式时间内解决该问题更强的结果表明这个问题也難以近似地得出答案但是有一个线性时间的方法可以用于有向无环图这对于发现调度问题中的关键路径有重要的作用