#ifndef LONG_PATH_H#define LONG_PATH_H#include<iostream>#include<string>#define MAX 65535int graphPath_longest(int (*Graph)[5],int Length,int origin,int destin ); void printf_path(int origin,int destin); #endif
#include"LongPath.h"#define Max(a,b) a>b? a:bint pathStore[20]; int graphPath_longest(int (*Graph)[5],int Length,int origin,int destin){ int pathLength=-1; for(int i=0;i<Length; i++){ if(Graph[origin][i]!=0&&Graph[origin][i]!=MAX&&origin!=destin){ if(graphPath_longest(Graph,Length,i,destin)+Graph[origin][i]>pathLength){ pathLength=graphPath_longest(Graph,Length,i,destin)+Graph[origin][i]; pathStore[origin]=i; } } else if(origin==destin){ pathStore[origin]=destin; pathLength=Max(0,pathLength); } } return pathLength; }void printf_path(int origin,int destin){ int n=origin; std::cout<<"the longest path in Graph from node "<<origin<<" to node "<<destin<<std::endl; std::cout<<origin; while(n!=destin){ n=pathStore[n]; std::cout<<"->"<<n; } std::cout<<std::endl; }
#include "LongPath.h"int main(){ int Graph[5][5]={MAX}; Graph[0][0]=0; Graph[0][4]=6; Graph[1][0]=9; Graph[1][1]=0; Graph[1][2]=3; Graph[2][0]=10; Graph[2][2]=0; Graph[2][3]=5; Graph[3][3]=0; Graph[3][4]=1; Graph[4][4]=0; std::cout<<"The longest path value "<<graphPath_longest(Graph,5,1,4)<<std::endl; printf_path(1,4); }
注：
本题中，我采用的解法还是使用了一般的解法思想，在该题中，我们还是采用的是固定一端不动，另一端进行优化的思想。
也就是说，
if
(
graphPath_longest
(
Graph
,
Length
,
i
,
destin
)+
Graph
[
origin
][
i
]>
pathLength
){
pathLength=graphPath_longest(Graph,Length,i,destin)+Graph[origin][i];
pathStore[origin]=i;
}
题中的destin一直都没有改变呢。
于是在记录优化路径时，我们只用了一维数组来解决问题，因为在每次迭代中变的只有那个origin，只要记录每次的origin就可以了
pathStore[origin]=i
每次的迭代都会求得一个最理想的i，从而我们只要记录这个理想的i就可以了。
而且下次的origin正好是这次的i，这样就循环套在一起了。
std::cout<<origin;
while(n!=destin){
n=pathStore[n];
std::cout<<"->"<<n;
}
上面的代码就是循环输出的。
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655527.html
