最长路径问题

维基百科,自由的百科全书
跳转至: 导航搜索

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

参见[编辑]

参考文献[编辑]

外部链接[编辑]