起点和终点未指定。这个是NPC么?

OIBH上

有人说是bellman-ford，我怎么想也觉得不对

简言之，对任意n顶点的有向图D，假如能够D中的找到最长无环路P，那么就能立即知道D中是否存在Hamilton路（只需看P的长度是否为n-1即可），从而最长无环路问题是NPC。

需要明确一点：
你所求的最长路是指边数最多还是总权最大，二者在初始化路长数组时有差别。

如果是不考虑圈，因为Floyd算法遍历了所有的路，如要求v1，v2间的最长路。Floyd算法探索了所有从v1到v2的路，进而从中间选出来一条最长的。

如果这条最长的路含有圈。。需要删除这条路，从新作Floyd搜索。。这个删除过程我认为也是有回溯的。。很复杂。。。

Dijkstra算法需要改进为遍历每一条边，即总循环次数由VerticesNum改为EdgesNum，即先前点的标注改为边的标注，并且每一条边的两个端点都是需要检测的，此时可求。

如果考虑圈。。。太复杂了。。。。

能不能对图预处理？把有圈图变成无圈图？例如把圈中一个顶点分成2个？
单从有圈图的角度考虑，太复杂了。。。

“对于两点v1，v2，若求得的最长路上有v3，则v1，v3是v1到v3的最长路；v3，v2是v3到v2的最长路。”这个命题是错误的。
考虑这样一个图：
A ------H
|       |
B       |
|       |
C       |
|       |
D - I - J
|       |
E       |
|       |
F       |
|       |
G ----- K
假定每条边的权都是1（从而这个反例对有权图和无权图都有效），那么A到G的最长路有两条：AHJIDEFG 和 ABCDIJKG，其中都含有顶点D，但这两条路中，前一条中不含从A到D的最长路(AHJID)，后一条中不含从D到G的最长路(DIJKG)。从而像Dijkstra算法那样先求局部最长路，然后连接起来的方法是不可行的。

关于“最长路问题是NPC问题”的论述，参见Garey和Johnson的Computer And Intractability - A Guide To The Theory Of NP-Completeness（http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=36231 有电子版下载）第213页（电子书中的第112个页面）：[ND29] Longest Path。

只听过NP，不知道啥叫NPC，这个题：
如果是无圈图，则（1）（2）同时成立，D，F在这里都可以用。
如果是有圈图，感觉算法异常复杂，甚至是回溯都不能很好解决的。所以我认为出路只有变有圈为无圈，或寻求一些局部求解

请问书上说的这个题的方法是什么？

那本书上证明了这个问题是NPC问题。

    NPC，即NP Complete。简单地来说，NPC问题是这样一类问题：
    首先，这些问题都是NP的。即，假设你提供给我无穷多台计算机，让它们同时工作，来解决这个问题，那么我可以轻易地在多项式时间里找到解，所谓多项式时间，就是它的时间增长速度不超过n的某个幂次，其中n是输入的规模，例如在这里，n就是输入的图顶点数。
    其次，如果这些问题中有任何一个问题是P问题（即，能用一台普通的计算机在多项式时间内解决），那么其它所有的NP问题（包括所有的NPC问题）都能用一台普通的计算机在多项式时间内解决。

    典型的NPC问题有：TSP（旅行商问题）、SAT（命题逻辑公式的可满足性问题）、哈密顿图问题（即，判定一个给定的图中是否有Hamilton回路）、哈密顿路问题（即，判定一个给定的图中是否有Hamilton通路）等。
    这些问题都被认为是很“难”的问题，因为多年来一直没人能找到解决这些问题的多项式时间算法。如果证明了一个问题是NPC的，就意味着证明了这个问题与上述那些“难”题一样“难”。因为如果一个问题是NPC的，而你在多项式时间内解决了它，就意味着你能在多项式时间内解决上述所有问题。鉴于一直没人能找到上述问题的多项式时间解，当你证明了一个问题是NPC时，就意味着你证明了：至今为止，这世上还没有人能在多项式时间内解决它。
    而Dijstra算法的时间复杂度是O(n^2)，Floyd算法的时间复杂度是O(n^3)，它们都是众人熟知的多项式时间算法。所以只要证明了“最长路问题是NPC”，就意味着上述算法肯定不能用（否则早就有人用它解决了TSP等问题了）。

    如果想知道更多有关NPC的内容，就看我前面提到的那本书吧。那是关于NPC问题的经典著作。