欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

校园导航

程序员文章站 2022-06-23 21:10:07
#include#includeusing namespace std;#define max 50//最大顶点数int njust[max][max];string njust_Name[max];const int infinity=0xfffffff;st...

#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(i
j)  
                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