求图中最长路径

图中最长路径"/>

求图中最长路径

求最长路径函数：

vector<int>Path;
vector<int>LongPath;
bool first=true;
float pathSum,longPathSum;
int paths=0;
vector<vector<int>> status(6,vector<int>(6,0));   //顶点状态void getRoad(vector<vector<float>> prox,int start,int end)
{Path.push_back(start);		status[start][end]=1;if(prox[start][end]>0){pathSum+=prox[start][end];Path.push_back(end);vector<int>::iterator iter;if(first){for(iter=Path.begin();iter!=Path.end();++iter){LongPath.push_back(*iter);}first=false;longPathSum=pathSum;}else{if(pathSum>longPathSum){LongPath.clear();for(iter=Path.begin();iter!=Path.end();++iter){LongPath.push_back(*iter);}longPathSum=pathSum;}}Path.pop_back();pathSum-=prox[start][end];}for(int i=0;i<prox.size();i++){if((status[start][i]==0)&&(status[i][end]==0)&&(prox[start][i]>0)){pathSum+=prox[start][i];getRoad(prox,i,end);pathSum-=prox[start][i];}}Path.pop_back();status[start][end]=0;
}

vector<vector<float>> mz(6,vector<float>(6,0.0)); //图中的权值
//测试最长路径mz[0][1]=0.3;mz[1][2]=1.0;mz[2][3]=0.3;mz[3][0]=0.3;mz[1][4]=0.6;mz[4][2]=0.7;mz[2][5]=0.4;mz[5][3]=0.3;getRoad(mz,4,1);