校园导航

#include
#include<string.h>
using namespace std;
#define max 50                 //最大顶点数
int njust[max][max];
string njust_Name[max];
const int infinity=0xfffffff;
struct ArcCell                  //定义边结点
{
    int value; 
};
struct MGraph
{
    string nameNodes[max];     //顶点表
    ArcCell mapArc[max][max];  //邻接矩阵，即表
    int vexnum;                //顶点数
    int arcnum;                //边数
};
void data()                   //地图数据
{
njust_Name[0]=“一号门”;          
 njust_Name[1]=“二号门”;      
njust_Name[2]=“三号门”;       
njust_Name[3]=“四号门”;    
njust_Name[4]=“五号门”;
    njust_Name[5]=“艺文馆”;         
njust_Name[6]=“水杉林”;        
njust_Name[7]=“冶园”;         
njust_Name[8]=“紫霞湖”;      
njust_Name[9]=“时间广场”;
    njust_Name[10]=“科技会堂”;     
  njust_Name[11]=“紫麓宾馆”;    
  njust_Name[12]=“研究生食堂”; 
  njust_Name[13]=“思源楼”;     
njust_Name[14]=“教育超市”;
    njust_Name[15]=“二道门”;        
njust_Name[16]=“综合楼”;       
njust_Name[17]=“旧图书馆”;    
njust_Name[18]=“新图书馆”;   
njust_Name[19]=“阳光体育长廊”;
    njust_Name[20]=“乒乓馆”;       
  njust_Name[21]=“明苑餐厅”;      
njust_Name[22]=“逸夫楼”;      
njust_Name[23]=“喷泉广场”;   
njust_Name[24]=“兵器博物馆”;
    njust_Name[25]=“二三食堂”;     
  njust_Name[26]=“校医院”;       
njust_Name[27]=“新体育馆”;    
njust_Name[28]=“星苑食堂”;       
njust_Name[29]=“南区体育场”;
    njust_Name[30]=“宜园”;          
njust_Name[31]=“二运”;          
njust_Name[32]=“创业园”;
 
 
 
   njust[0][1]=njust[1][0]=300;     njust[1][6]=njust[6][1]=250;     njust[1][5]=njust[5][1]=250;     njust[2][3]=njust[3][2]=100;
   njust[2][4]=njust[4][2]=800;    njust[2][7]=njust[7][2]=600;     njust[2][8]=njust[8][2]=600;     njust[2][32]=njust[32][2]=950;
   njust[2][20]=njust[20][2]=1100;  njust[2][25]=njust[25][2]=1200;  njust[3][4]=njust[4][3]=300;     njust[4][32]=njust[32][4]=10;
   njust[4][13]=njust[13][4]=100;   njust[5][6]=njust[6][5]=30;      njust[5][9]=njust[9][5]=20;      njust[6][9]=njust[9][6]=25;
   njust[6][15]=njust[15][6]=120;   njust[7][8]=njust[8][7]=20;      njust[8][13]=njust[13][8]=100;   njust[9][10]=njust[10][9]=10;
   njust[10][11]=njust[11][10]=20;  njust[10][15]=njust[15][10]=50;  njust[11][12]=njust[12][11]=20;  njust[13][32]=njust[32][13]=10;
   njust[13][14]=njust[14][13]=300; njust[13][15]=njust[15][13]=300; njust[13][20]=njust[20][13]=100; njust[15][16]=njust[16][15]=30; 
   njust[15][17]=njust[17][15]=40;  njust[16][17]=njust[17][16]=10;  njust[16][18]=njust[18][16]=200;
   njust[17][18]=njust[18][17]=230; njust[17][19]=njust[19][17]=20;  njust[18][19]=njust[19][18]=50;  njust[19][21]=njust[21][19]=60;
   njust[19][30]=njust[30][19]=20;  njust[20][25]=njust[25][20]=300; njust[21][22]=njust[22][21]=200; njust[22][23]=njust[23][22]=20;
   njust[22][26]=njust[26][22]=60;  njust[23][24]=njust[24][23]=20;  njust[23][26]=njust[26][23]=100;  njust[24][26]=njust[26][24]=15;
   njust[25][26]=njust[26][25]=300; njust[26][27]=njust[27][26]=150; njust[27][28]=njust[28][27]=400;  njust[28][29]=njust[29][28]=100;
}
class Graph
{
    private:
        MGraph Map;
public:      
     void CreateMap();//创建地图
        int LocateNode(string Node);//定位Node点
        void PrintMap(){
        }//显示地图
        int ShortPath(string A,string B);//计算A,B的最短路径
};
int Graph::LocateNode(string Node)
{
    for(int i=0;i<max;i++)
    {
        if(Map.nameNodes[i]Node)
        {
            return i;//返回顶点位置
        }
    }
    return -1;
}
void Graph::CreateMap()
{
   Map.vexnum=32;
    Map.arcnum=100;
    int i,j;
    data();
    for(int i=0;i<Map.vexnum;i++)
    {
        Map.nameNodes[i]=njust_Name[i];
    }
    for(i=0;i<Map.vexnum;i++)
    {
        for(j=0;j<Map.vexnum;j++)
        {
           if(njust[i][j])
         {
            Map.mapArc[i][j].value=njust[i][j];
         }
         else
            {
                if(ij)  
                Map.mapArc[i][j].value=0;
             else
                     Map.mapArc[i][j].value=infinity;
            }
        }
   }
}
int Graph::ShortPath(string A,string B)
{
    int D[max][max],P[max][max][max];
    int LA=LocateNode(A);
    int LB=LocateNode(B);
   for(int v=0;v<Map.vexnum;v++)
   {
      for(int w=0;w<Map.vexnum;w++)
      {
         D[v][w]=Map.mapArc[v][w].value;
         for(int u=0;u<Map.vexnum;u++)
         {
            P[v][w][u]=false;
         }
         if(D[v][w]<infinity)
         {
            P[v][w][v]=P[v][w][w] = true;
         }
      }
   }
   for(int u=0;u<Map.vexnum;u++)
   {
      for(int v=0;v<Map.vexnum;v++)
      {
         for(int w=0;w<Map.vexnum;w++)
         {
            if(D[v][u]+D[u][w]<D[v][w])
            {
               D[v][w]=D[v][u]+D[u][w];
               for(int i=0;i<Map.vexnum;i++)
               {
                  P[v][w][i]=P[v][u][i]||P[u][w][i];
               }
            }
         }
      }
   }
    if(LA!=LB)
    {
        cout<<“从”<<Map.nameNodes[LA]<<“到”<<Map.nameNodes[LB]<<“最短路径是:”<<endl;
        for(int k=0;k<Map.vexnum;k++)
            if(P[LA][LB][k]==1)
                cout<<"–>"<<Map.nameNodes[k];
        cout<<endl;
    }
    else
    {
       cout<<“已到达”<<endl;
    }
}
int main()
{
    Graph Mapsearch;   
    Mapsearch.CreateMap();
   string start,end;
     cout<<“查找最短路径:”<<endl;
    cout<<“请输入起点：”<<endl;
    cin>>start;
    cout<<“请输入终点：”<<endl;
   cin>>end;
    Mapsearch.ShortPath(start,end);  
    return 0;
}

本文地址：https://blog.csdn.net/xyz53235/article/details/107306122