C++基于Floyd算法实现校园导航系统

C++基于Floyd算法实现校园导航系统

本文实例为大家分享了C++基于Floyd算法实现校园导航系统的具体代码,供大家参考,具体内容如下

首先是配置文件

//文件名'MGraph.h' //用途:创建邻接矩阵 #include<iostream> #include<stdlib.h> using namespace std; /* *author:xcy  *date:2019.6.1  */ #define MaxInt 32767 //表示极大值 #define MaxNum 100  //表示最大顶点数 typedef int status; typedef string VerTexType;  //顶点的数据类型 typedef int ArcType;  //边的权值为整型 typedef struct {     VerTexType vexs[MaxNum];   //顶点表     ArcType arcs[MaxNum][MaxNum];   //邻接矩阵     int vexnum,arcnum;//当前的点和边数     char name[MaxNum]; }AMGraph; status CreateMap(AMGraph &G)//地图的创建  {     G.vexnum=10;      G.arcnum=13;     G.vexs[0]="北门";     G.vexs[1]="下沉广场";     G.vexs[2]="青年公寓";     G.vexs[3]="齐贤广场";     G.vexs[4]="15教";     G.vexs[5]="菜鸟驿站";     G.vexs[6]="汇森楼";     G.vexs[7]="图书馆";     G.vexs[8]="体育馆";     G.vexs[9]="南苑餐厅";     for(int i=0;i<MaxNum;i++)//初始化所有顶点之间距离      {         for(int j=0;j<MaxNum;j++)         {             G.arcs[i][j] = MaxInt;         }     }     //各顶点之间距离     G.arcs[0][1] = G.arcs[1][0] = 300;         G.arcs[0][2] = G.arcs[2][0] = 600;         G.arcs[1][2] = G.arcs[2][1] = 200;         G.arcs[2][3] = G.arcs[3][2] = 600;         G.arcs[2][6] = G.arcs[6][2] = 1000;     G.arcs[3][4] = G.arcs[4][3] = 100;         G.arcs[3][6] = G.arcs[6][3] = 800;         G.arcs[4][5] = G.arcs[5][4] = 100;         G.arcs[4][8] = G.arcs[8][4] = 400;     G.arcs[5][9] = G.arcs[9][5] = 700;     G.arcs[6][7] = G.arcs[7][6] = 100;     G.arcs[7][8] = G.arcs[8][7] = 100;     G.arcs[8][9] = G.arcs[9][8] = 300; }

具体方法实现

#include<iostream> #include<stdlib.h> #include"MGraph.h"  using namespace std; /* *author:xcy  *date:2019.6.12 *change:使用弗洛依德算法  */ int shortPath[MaxNum][MaxNum];//最短路径长度  int Path[MaxNum][MaxNum];//保存下一个节点  void ShortestPath_Floyd(AMGraph G)//弗洛依德算法 {     int i,j,k;     for(i=0;i<G.vexnum;i++)//循环遍历所有顶点(横列)      {         for(j=0;j<G.vexnum;j++)//循环遍历所有顶点(竖列)         {             shortPath[i][j]=G.arcs[i][j];//保存权值              if(shortPath[i][j]<MaxInt&&i!=j)                  Path[i][j]=j;//保存下一个顶点下标              else Path[i][j]=-1;         }     }     //算法核心语句      for(k=0;k<G.vexnum;k++)//遍历所有点(作为中点)      {         for(i=0;i<G.vexnum;i++)//遍历行          {             for(j=0;j<G.vexnum;j++)//遍历列              {                 //松弛操作 如果经历k点距离小于两点之间距离,选择经过k点的路线                  if(shortPath[i][k]+shortPath[k][j]<shortPath[i][j])                 {                     shortPath[i][j]=shortPath[i][k]+shortPath[k][j];                     Path[i][j]=Path[i][k];//更新操作                  }             }         }     } } void math()//次级界面 {     int a,b,i,j,k,m,n;     AMGraph G;     CreateMap(G);     ShortestPath_Floyd(G);    //弗洛依德算法     cout<<"1.北门 2.下沉广场 3.青年公寓 4.齐贤广场 5.15教"<<endl;     cout<<"6.菜鸟驿站 7.汇森楼 8.图书馆 9.体育馆 10.南苑餐厅"<<endl;     cout<<"输入起点的序号"<<endl;     cin>>a;     cout<<"输入终点的序号"<<endl;     cin>>b;     m=a-1;     n=b-1;     cout<<"最短路径:"<<shortPath[m][n]<<"米"<<endl;     cout<<"路径为:"<<G.vexs[m];     k=Path[m][n];     while(k!=n)     {         cout<<" -> "<<G.vexs[k];         k=Path[k][n];     }    cout<<" -> "<<G.vexs[n]<<endl; } void scence()//显示地图  {     cout<<"\t\t--------------------------------------------------------"<<endl;     cout<<"\t\t|       北门                                           |"<<endl;      cout<<"\t\t|                                                      |"<<endl;     cout<<"\t\t|  下沉                                                |"<<endl;     cout<<"\t\t|  广场           青年                                 |"<<endl;     cout<<"\t\t|                 公寓                                 |"<<endl;     cout<<"\t\t|                                                      |"<<endl;     cout<<"\t\t|                                   菜鸟               |"<<endl;     cout<<"\t\t|                          15教     驿站               |"<<endl;     cout<<"\t\t|                                                      |"<<endl;     cout<<"\t\t|                    齐贤广场                          |"<<endl;     cout<<"\t\t|                                               南苑   |"<<endl;     cout<<"\t\t|                                               餐厅   |"<<endl;     cout<<"\t\t|               汇森楼                                 |"<<endl;     cout<<"\t\t|                         图书馆    体育馆             |"<<endl;     cout<<"\t\t--------------------------------------------------------"<<endl; } void Gui()//主界面 {     char a;     cout<<"\t\t\t┌--------------------------------┐"<<endl;     cout<<"\t\t\t│                                │"<<endl;     cout<<"\t\t\t│   欢迎使用南工校园导航系统     │"<<endl;     cout<<"\t\t\t│                                │"<<endl;     cout<<"\t\t\t│--------------------------------│"<<endl;     cout<<"\t\t\t│      1. 查看校园全貌           │"<<endl;     cout<<"\t\t\t│      2. 计算最短路径           │"<<endl;     cout<<"\t\t\t│      3. 退出导航系统           │"<<endl;     cout<<"\t\t\t└--------------------------------┘"<<endl;     while(true){     cout<<"\t\t\t输入要操作的序号(1-3):";         cin>>a;         (int)a;         if(a>'0'&&a<='3')             switch(a)             {                   case '1': scence(); break;                   case '2': math(); break;                   case '3': cout<<"\t\t\t感谢您的使用!";exit(0);break;               }           else cout<<"\t\t\t请输入1-3!!"<<endl;      }    } int main() {     Gui(); }

推荐阅读