数据结构：可以用求最短路径的方法思想求最长路径么？为什么呢？

这里求解最短路径的通用方法有Dijkstra算法和Floyd-Warshall算法，Dijkstra算法不允许边的权值为负，也不允许有回路，而Floyd-Warshall算法可以允许边的权值为负，但不允许负值边构成回路，即可以求解有回路的图

它们都有局限，这两种算法的思想可以用来求最长路径么？？ 为什么 不可以？

（感谢给我答案的好心人：来自于知乎：http://www.zhihu.com/question/27201255和CSDN）

以下整理出详细解答：

1)      不可以，核心在于最短路问题是有最优子结构的，就是『最短路的子路径还是最短路』，而最长路径不存在这个子结构。这里的最长路径是指两个节点之间最长简单路径（路径不循环）。考虑下算法导论上面的例子：有两条最长的路径与Q到T：Q– > R –> T和Q– > S-> T。不像最短路径，这些路径最长不具有最优子属性。例如，最长路径q-> r-> t不是由q->r和r->t的组合，因为最长的路径从q至r为q-> s-> t->r

2)        不可以。最短路径问题是P的，但最长路径问题是NP-hard的：

证明最长路径问题是NP-Hard的 Proof:假如最长路径问题有多项式时间算法A，我们证明Hamilton回路问题也有多项式时间算法，从而建立Turing归约。 对任意一个图G=，用如下算法检查其是否有Hamilton回路： 给所有边赋权值1，取定V中一个顶点v 对所有v '∈V,循环： 如果