全国铁路运输网最佳经由问题数据结构课程设计1(6)

outfile.close();

// cout<<\// cout<<\cout<<\成功添加新的线路\

cout<<\新建线路的序号 :\}

void floyed() //弗洛伊德算法 {

int i,j,k,m;

//包含着count 和path[]用来存储经过的路径 // for(i=0;i<=view_count;i++) // for(j=0;j<=view_count;j++)

// dist_list[i][j]=MAXCOST;//先对任意两点的距离初始值为无穷 for(int t=0;t<=way_count;t++) {

i=ways[t].station1; j=ways[t].station2;

dist_list[i][j]=ways[t].dist;//把文件中的数据付给dist_list[i][j]=ways[t].dist;形式 }

for(i=0;i<=view_count;i++) {

for(j=0;j<=view_count;j++) {

if(i==j) //车站到本车站的距离赋值为零 {

dist_list[i][j]=0; continue; }

dist_list[i][j]=-1; //先设置任意两点之间的距离为-1..表示这两点不通 path_list[i][j].count=0; //先设置任意两点之间的的路径的车站数为零 for(k=0;k

if(ways[k].station1==i&&ways[k].station2==j) {

dist_list[i][j]=ways[k].dist; path_list[i][j].count=2; path_list[i][j].path[0]=i; path_list[i][j].path[1]=j; break; } }

} }

//下面是计算最短路径的代码 for(k=0;k<=view_count;k++) {

for(i=0;i<=view_count;i++) for(j=0;j<=view_count;j++) {

if(i==k||j==k||i==j) //三个站中至两个站是相同的的话就是继续循环 continue;

if(dist_list[i][k]==-1||dist_list[k][j]==-1) //i、k 不通或者k、j 不通继续循环

continue;

if((dist_list[i][j]==-1)||((dist_list[i][j] != -1)&&(dist_list[i][k]+dist_list[k][j]

{ //i、j 不通..或者是i、j 通但是不是最短路径..执行下面语句

dist_list[i][j]=dist_list[i][k]+dist_list[k][j]; //求出i、j 的最短距离

//shortest[i][j]=shortest[i][k]+shortest[k][j];

path_list[i][j].count=path_list[i][k].count+path_list[k][j].count-1; //求出i、j 路径的站的个数

//path_list[i][j]=k;

for(m=0;m

path_list[i][j].path[m]=path_list[i][k].path[m]; for(m=0;m

path_list[i][j].path[m+path_list[i][k].count]=path_list[k][j].path[m+1]; } } } }

void shortest_path() {

floyed(); int i,k,m;

int start_num=-1,end_num=-1;

string start_station,end_station;//定义起始站、终点站 //下面便是输出最短经由路径的代码 cout<<\

//cout<<\cout<<\所有城市列表:\\n\

for(i=0;i

cout<

cout<

cout<

//cout<<\cout<<\请输入起点站名称:\cin>>start_station;

for(i=0;i

if(start_station==views[i].name) start_num=i; }

while(start_num==-1) //容错处理 {

cout<<\你的输入有误..请重新输入..\

//cout<<\cout<<\请输入起点站名称:\cin>>start_station;

for(i=0;i

if(start_station==views[i].name) start_num=i; } }

//cout<<\cout<<\请输入终点站的名称:\cin>>end_station;

for(i=0;i

if(end_station==views[i].name) end_num=i; }

while(end_num==-1) //容错处理 {

cout<<\你的输入有误..请重新输入..\//cout<<\cout<<\请输入终点站的名称:\cin>>end_station;

for(i=0;i

{

if(end_station==views[i].name) end_num=i; } }

cout<

cout<<\从 \到 \输出最短经由路径

if(dist_list[start_num+1][end_num+1]==-1) //没有找到的情况的回应 cout<<\else {

//cout<<\distance is \and path is:\

cout<<\距离是 \最短路径:\k=path_list[start_num+1][end_num+1].path[0]-1; cout<

for(m=1;m

k=path_list[start_num+1][end_num+1].path[m]-1; cout<<\} }

cout<

void adddata(int menu) {

if(menu==1) {

while(1) {

addview();

cout<>con; if(con=='y'); else break; } }

if(menu==2) {

while(1) {

addline(); addway();

cout<>con; if(con=='y'); else break; } } }