#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
