x++;?}?//以上代码初始化l将边长度信息写入,无边则为-1 for(intk=1;k<=n;k++) for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) if(l[i][k]!=-1&&l[k][j]!=-1&&((l[i][j]==-1)||(l[i][k]+l[k][j])<l[i][j])) { l[i][j]=l[i][k]+l[k][j]; l[j][i]=l[i][k]+l[k][j]; kay[i][j]=k; kay[j][i]=k; }}//floyd算法以下是输出路径的递归算法:voidDiGraph::getpath(intfrom,intto,int**kay,int**l,string&path){ if(kay[from][to]==0)?{ GraphNode*road_temp; v[from].Find(to,road_temp); path=path+road_temp->roadname+"\t"; return;?}?getpath(from,kay[from][to],kay,l,path);?path=path+v[kay[from][to]].name+"\t";?getpath(kay[from][to],to,kay,l,path);?return;}C.经过多个顶点的最短路径算法这里我利用folyd算法产生的两个二维数组,生成途径景点的全排列,然后利用l[][]求出排列中路径最短的路,再用与floyd算法相同的输出最短路径的算法进行输出,其关键代码如下:voidDiGraph::getroute(int**l,int*min_route,int*route,intn,ints,inte)//暴力的O(n!)算法保证得到最短路径//经过多个顶点的最短路径利用全排列算法和floyd算法得到
全文预览
