最长路径问题

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