guide.cpp

采用floyd算法实现的校园导游系统,区别于迪杰斯特拉算法,包中有源代码,以及可以直接运行的exe文件!

/*包含头文件*/
#include<stdio.h> 
#include<process.h>
#include"iostream"
#include"cstring"

using namespace std;
/*定义符号常量*/
#define INT_MAX 10000
#define n 10

/*定义全局变量*/
int cost[n][n];/* 边的值*/
int shortest[n][n];/* 两点间的最短距离*/
int path[n][n];/* 经过的景点*/


/*自定义函数原型说明*/
void introduce();
int shortestdistance();
void floyd(); 
void display(int i,int j);

void main() 
{/*主函数*/
 int i,j; 
 char k; 
 for(i=0;i<=n;i++)
 for(j=0;j<=n;j++)
 cost[i][j]=INT_MAX; 
 cost[1][2]=cost[2][1]=300;
 cost[2][3]=cost[3][2]=220;
 cost[2][4]=cost[4][2]=120;
 cost[3][4]=cost[4][3]=99;
 cost[1][4]=cost[4][1]=250;
 cost[2][5]=cost[5][2]=230;
 cost[5][10]=cost[10][5]=510;
 cost[5][6]=cost[6][5]=200;
 cost[6][7]=cost[7][6]=110;
 cost[7][8]=cost[8][7]=95;
 cost[7][9]=cost[9][7]=190;
 cost[8][9]=cost[9][8]=85;
 cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; 
 cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;
 while(1)
 {
 cout<<"\n";

 cout<<"*****************************欢迎使用济南大学导游系统***************************";
 cout<<"                                   *仅供参考* "<<"\n";
 cout<<"********************************************************************************";
 cout<<"\n";
 cout<<"1.景点信息查询………………………请按 i "<<"\n";
 cout<<"2.景点最短路径查询…………………请按 s "<<"\n";
 cout<<"3.退出系统……………………………请按 e "<<"\n";
 cout<<"\n";
 cout<<"学校景点列表:"<<"\n";
 cout<<"\n";
 cout<<"1:学校新西门"<<"\t";
 cout<<"2:老信息楼"<<"\t";
 cout<<"3:体育场"<<"\t";
 cout<<"4:绿泉广场"<<"\t";
 cout<<"5:好莱坞"<<"\t";
 cout<<"6:济大超市"<<"\t";
 cout<<"7:荷园餐厅"<<"\t";
 cout<<"8:第五教学楼"<<"\t";
 cout<<"9:新图书馆"<<"\t";
 cout<<"10:行政楼"<<"\n";
 cout<<"\n";
 cout<<"请选择服务:"<<"\n";
 cin>>k; 
  switch(k){ 
    case 'i':
         cout<<"进入景点信息查询:";
         introduce();
    break; 
    case 's':
         cout<<"进入最短路径查询:";
         shortestdistance();
    break; 
    case 'e':
         exit(0); 
    default:
         cout<<"输入信息错误！\n请输入字母i或s或e"<<"\n";
    break; 
 } 
 } 
}/*main*/

void introduce()
{/*景点介绍*/
 int a;
 cout<<"您想查询哪个景点的详细信息?请输入景点编号:";
 cin>>a;
 getchar();
 cout<<"\n";
   switch(a){
      case 1: 
        cout<<"1:学校新西门"<<"\n"<<"学校的主要出口，为于济微路的东边，多路公交车辆汇聚于此。"<<"\n"; break;
      case 2: 
         cout<<"2:老信息楼"<<"\n"<<"学校以前的高科技汇聚基地"<<"\n";break; 
      case 3: 
         cout<<"3:体育场"<<"\n"<<"学校建设最好的体育场地，设有多种健身器材及塑胶跑道。"<<"\n";break; 
      case 4: 
         cout<<"4:绿泉广场"<<"\n"<<"学校以前最优美的经典之一，中间设有喷泉，位于钟楼的南面。"<<"\n";break; 
      case 5: 
         cout<<"5:好莱坞"<<"\n"<<"济大价格昂贵的饮食场所，供学生奢侈的场所。"<<"\n";break; 
      case 6: 
         cout<<"6:济大超市"<<"\n"<<"济大学生购物的场所，二楼是大学生活动中心，学生狂欢的场所。"<<"\n";break; 
      case 7: 
         cout<<"7:荷园餐厅"<<"\n"<<"学校的招待所。　"<<"\n";break; 
      case 8: 
         cout<<"8:第五教学楼"<<"\n"<<"学校斥巨资建设的多媒体教学楼。"<<"\n";break; 
      case 9: 
         cout<<"9:新图书馆"<<"\n"<<"　学校信息资源中心，内设大量的自习室，。"<<"\n";break; 
      case 10: 
         cout<<"10:行政楼"<<"\n"<<"学校最豪华的建设，内设有豪华办公室，学校高层领导工作的地方。"<<"\n";break; 
      default:
         cout<<"景点编号输入错误！请输入1->10的数字编号！"<<"\n"; break; 
 }
}

int shortestdistance()
{/*要查找的两景点的最短距离*/
 int i,j; 
 cout<<"请输入要查询的两个景点的编号:";
 cout<<"\n";
 cout<<"注意:请输入1到10的数字编号并用','间隔!!!";
 cout<<"\n";
 cout<<"请输入：";
 scanf("%d,%d",&i,&j);
 //cin>>i;
 //cin>>j;
 if(i>n||i<=0||j>n||j<0)
 {
 cout<<"输入信息错误!";
 cout<<"\n";
 cout<<"请输入要查询的两个景点的编号:";
 cout<<"\n";
 cout<<"注意:请输入1到10的数字编号并用','间隔!!!";
 cout<<"\n";
 cout<<"请输入：";
 scanf("%d,%d",&i,&j);
 }
 else
 {
 floyd();
 display(i,j);
 }
 return 1;
}

void floyd()
{/*用弗洛伊德算法求由一个景点到另一景点的最短路径*/
 int i,j,k; 
 for(i=1;i<=n;i++) 
 for(j=1;j<=n;j++) 
 {
 shortest[i][j]=cost[i][j];
 path[i][j]=0; 
 }
 for(k=1;k<=n;k++) 
 for(i=1;i<=n;i++) 
 for(j=1;j<=n;j++)
 if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) 
 {/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
 shortest[i][j]=shortest[i][k]+shortest[k][j];
 path[i][j]=k;
 path[j][i]=k;
 } 
}

void display(int i,int j)
{/* 打印两个景点的路径及最短距离 */
 int a,b;
 a=i;
 b=j;
 cout<<"您要查询的两景点间最短路径是:";
 cout<<"\n";
 if(shortest[i][j]!=INT_MAX)
 {
 if(i<j)
 { 
 cout<<b;
 while(path[i][j]!=0)
 {/* 把i到j的路径上所有经过的景点按逆序打印出来*/
 cout<<"<-"<<path[i][j];//path[i][j]中的各个元素为途经的经点
  if(i<j)
 j=path[i][j]; 
 else 
 i=path[j][i];
 } 
 cout<<"<-"<<a;
 cout<<"\n";
 cout<<"\n";
 cout<<a<<"->"<<b<<"的最短距离是"<<shortest[a][b];//打印最短路径shortest[a][b]
 }
 else 
 {
 cout<<a;
 while(path[i][j]!=0)
 {/* 把i到j的路径上所有经过的景点按顺序打印出来*/
 cout<<"->"<<path;
 if(i<j)
 j=path[i][j]; 
 else 
 i=path[j][i]; 
 } 
 
 cout<<"->"<<b;
 cout<<"\n"<<"\n"; 
 cout<<a<<"->"<<b<<"的最短距离是:"<<shortest[a][b]<<"米"<<"\n"<<"\n";
 } 
 } 
 else
 cout<<"输入错误！不存在此路！";
 cout<<"\n"<<"\n";
 
}