【正确答案】正确答案：基本设计思想：我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度，这里的边权是正数，如果图中所有的边权均为负数，那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度，此时若把所有的边权取相反数，则刚才求得的最短路径长度的相反数一定是现在的最长路径长度；根据此思想，将图G的边权改为它的相反数，得到图G'，然后用floyd算法对G'求出每对顶点间的最短路径，那么图G'中最短路径的相反数即为原图G的最长路径长度。

【正确答案】正确答案：算法实现如下： int floyd(Graph G) { ／／构造一个新图 int dist[n][n]； ／／n是已经定义的常量，代表图中顶点的个数 for(int i=0；i＜G．VerticeNum()；i++) { for(int j=0；j＜G．VerticeNum()；j++) { dist[i][j]=-G．weight(i，j); ／／初始化新图的边权 } } ／／弗洛伊德算法 for (int k=0；k＜G．G．VerticeNum()；k++) { for(int i=0；i＜G．G.VerticeNum()；i++) for(int j=0；j＜G．G．VerticeNum()；j++) if(dist[i][j]＞dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]； } ／／遍历新图，找出最大路径长度 int max=0； for(int i=0；i＜G．VerticeNum()，i++) for(int j=0；j＜G．VerticeNum()；j++) if(max＜-dist[i][j]) max=-dist[i][j]; return max； }

【正确答案】正确答案：时间复杂度分析：因为用到了floyd算法，而遍历新图用到的是两层循环(小于O(n ³ ))，故时间复杂度为O(n ³ )(n代表节点的个数)。