交通咨询系统设计
实验目的和要求
1. 掌握最短路径的算法；
2. 编写实验报告；
实验内容
本设计要求一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径、最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或所需费用。
实验步骤
1、 问题分析
该设计分为三个部分：
建立交通网络图的存储结构
解决单源最短路径问题
实现两个城市顶点之间的最短路径问题
2、 问题求解
2.1建立交通网络图的存储结构
图的邻接矩阵
#define MVNum 50
Typedef struct{
VertexType vexs[MVNum];//顶点信息
Adjmatrix arcs[MVNum][MVNum];//邻接矩阵边的信息
}MGraph
2.2单源最短路径
Dijkstra算法
按路径长度递增产生诸顶点的最短路径
2.3任意两个顶点之间的最短路径
Floyd算法
3、 完整的程序清单
4、 程序运行测试
#include \"stdafx.h\"
#include #include #define MVNum 50 #define Dij_MAXN 33 #define MAX_VERTEX_NUM 31 #define MAX_STRING_NUM 10 #define MAX_TRAFFIC_NUM 10 typedef struct TrafficNode { char name[MAX_STRING_NUM]; int Time;// int EndCity //火车到达城市的编号 int Cost;//票价 } TrafficNodeDat; typedef struct VNode { CityType city; //城市编号 int TrainNum; //标记下面Train数组里元素个数 TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次 } VNodeDat; typedef struct TrafficNode { char name[MAX_STRING_NUM]; //班次 int Time; int EndCity; //火车到达城市的编号 int Cost; //票价 } TrafficNodeDat; typedef struct VNode { CityType city; //城市编号 int FlightNum; //标记下面Train数组和Flight数组里元素个数 TrafficNodeDat Flight[MAX_TRAFFIC_NUM]; } VNodeDat; int main() switch(Command) { case 0: return 0; case 1: Administrators();//管理员操作界面函数 break; case 2: User();//用户操作界面函数 break; default: cout<<\"\选择序号错误!请重新选择!\\n\"; int InitSystem() void User() void Administrators() int DelCity(char *Name) //删除城市 { //删除城市 int city,i,j; city=SeekCity(Name); for(i=city;i strcpy(CityName[i],CityName[i+1]); AdjList[i].FlightNum=AdjList[i+1].FlightNum;AdjList[i].TrainNum=AdjList[i+1].TrainNum; for(j=0;j AdjList[i].Flight[j].Cost=AdjList[i+1].Flight[j].Cost; AdjList[i].Flight[j].EndCity=AdjList[i+1].Flight[j].EndCity; strcpy(AdjList[i].Flight[j].name,AdjList[i+1].Flight[j].name); AdjList[i].Flight[j].Time=AdjList[i+1].Flight[j].Time; } } CityNum--; return 1; } int DelPath(char *name) { //删除路线 int i,j,flag=0; for(i=0;i //删除路线 for(j=0;j {flag=1;break;}//找到要删除的路线，找到跳出for循环 if(flag) { for(;j AdjList[i].Flight[j].Cost=AdjList[i].Flight[j+1].Cost; AdjList[i].Flight[j].EndCity=AdjList[i].Flight[j+1].EndCity; strcpy(AdjList[i].Flight[j].name,AdjList[i].Flight[j+1].name); AdjList[i].Flight[j].Time=AdjList[i].Flight[j+1].Time; } AdjList[i].FlightNum--;//将要删除路线后面的路线全部向前移，并将总数减1 break; } for(j=0;j { flag=1; break; } if(flag) { for(;j AdjList[i].Train[j].Cost=AdjList[i].Train[j+1].Cost; AdjList[i].Train[j].EndCity=AdjList[i].Train[j+1].EndCity; strcpy(AdjList[i].Train[j].name,AdjList[i].Train[j+1].name); AdjList[i].Train[j].Time=AdjList[i].Train[j+1].Time; } AdjList[i].TrainNum--; break; } }return 1; } int InsertCity(char *Name) //添加某个城市 { //添加城市 strcpy(CityName[CityNum],Name); AdjList[CityNum].city=CityNum;//设置城市编号 AdjList[CityNum].FlightNum=0; AdjList[CityNum].TrainNum=0;//新增城市火车数和飞机数初始为零 CityNum++;//城市总数加1 return 1; } int InsertFlight(char *flight,char *StartCity,char *EndCity,int Time,int cost) //添加某架航班 { //添加飞机路线 int i,j; i=SeekCity(StartCity);j=SeekCity(EndCity); AdjList[i].Flight[AdjList[i].FlightNum].Cost=cost;AdjList[i].Flight[AdjList[i].FlightNum].EndCity=j; AdjList[i].Flight[AdjList[i].FlightNum].Time=Time; strcpy(AdjList[i].Flight[AdjList[i].FlightNum].name,flight); AdjList[i].FlightNum++; return 1; } int InsertTrain(char *train,char *StartCity,char *EndCity,int Time,int cost) //添加某次列车 { //添加火车路线 int i,j; i=SeekCity(StartCity);j=SeekCity(EndCity); AdjList[i].Train[AdjList[i].TrainNum].Cost=cost;AdjList[i].Train[AdjList[i].TrainNum].EndCity=j; AdjList[i].Train[AdjList[i].TrainNum].Time=Time; strcpy(AdjList[i].Train[AdjList[i].TrainNum].name,train); AdjList[i].TrainNum++; return 1; } void Dijkstra(int s[30][30],int p_start,int p_end,int TravelType) { int PreCity[30]; int i,j,min,pre,pos; for(i=0;i while(PreCity[p_end]==-1) { min=-1; for(i=0;i { for(j=0;j pre=i;pos=j;//j为起始站中花费最小的到达站的城市编号 min=s[i][j]; } } PreCity[pos]=pre; } Dijkstra_Output(s,PreCity,p_end,TravelType); } int CalcMinCost(int StartCity,int EndCity,int TravelType) { //查询最小耗费路线 int s[30][30]; int i,j,min,end,flag1,flag2; flag1=0;flag2=0; for(i=0;i if(TravelType==0)//判断初始城市和终点城市是否在火车交通路线中 for(i=0;i if(AdjList[i].Train[j].EndCity==StartCity) flag1=1; if(AdjList[i].Train[j].EndCity==EndCity) flag2=1; } else if(TravelType==1)//判断初始和终点城市是否在飞机交通路线中 for(i=0;i if(AdjList[i].Flight[j].EndCity==StartCity) flag1=1; if(AdjList[i].Flight[j].EndCity==EndCity) flag2=1; } if(flag1!=1&&flag2!=1) {printf(\"\\n\抱歉!没有您要查找的路线!\");return 0;} if(TravelType==0) { for(i=0;i min=32767;j=0; while(j min=32767;end=AdjList[i].Train[j].EndCity; while(end==AdjList[i].Train[j].EndCity&&j if(AdjList[i].Train[j].Cost }//min为i城市中的最小花费，end为其路线终点站 s[i][end]=min; } } } else { for(i=0;i min=32767;j=0; while(j min=32767;end=AdjList[i].Flight[j].EndCity; while(end==AdjList[i].Flight[j].EndCity&&j if(AdjList[i].Flight[j].Cost } s[i][end]=min; } } } Dijkstra(s,StartCity,EndCity,TravelType); return 1; } //存储数据函数 int SaveFile()/////////////////////////////////////////////////////////////// { //将火车飞机交通信息写入文件 FILE *fp; int i,j,total; if((fp=fopen(\"city.txt\ { cout<<\"\\n\无法打开文件!\\n\"; return -1; } fprintf(fp,\"%d\\n\在city文件中输入城市总数 for(i=0;i fclose(fp); total=0; if((fp=fopen(\"train.txt\ { cout<<\"\\n\无法打开文件!\\n\"; return -1; } for(i=0;i fprintf(fp,\"%d\\n\在train文件中输入火车总数 for(i=0;i fprintf(fp,\"%s %s %s \j].name,CityName[i], CityName[AdjList[i].Train[j].EndCity]); //输入火车车次，始发站和终点站 fprintf(fp,\"%d %d\\n\j].Time,AdjList[i].Train[j].Cost);//输入发车时间和到站时间和费用 } fclose(fp); total=0; if((fp=fopen(\"flight.txt\ { cout<<\"\\n\无法打开文件!\\n\"; return -1; } for(i=0;i fprintf(fp,\"%d\\n\在flight文件中输入飞机总数 for(i=0;i fprintf(fp,\"%s %s %s \j].name,CityName[i], CityName[AdjList[i].Flight[j].EndCity]); //输入飞机航班号，始发站和终点站 fprintf(fp,\"%d %d\\n\j].Time,AdjList[i].Flight[j].Cost);//输入起飞时间，到达时间和费用 } fclose(fp); return 1; } 因篇幅问题不能全部显示，请点此查看更多更全内容