#include<iostream>
#include<iomanip>
using namespace std;
#define MAXINT 10000 /*无穷大*/
#define MVNUM 40
#define MAX 40
typedef struct
{
char *name;
int num;
char *introduction;
}INFORMATION;
typedef struct ACCESS
{
int length;
}ACCESS,LENGTHA[MVNUM][MVNUM];
typedef struct
{
INFORMATION VEXS[MVNUM];
LENGTHA ARCS;// Maybe error
int VEXNUM,ARCNUM;
}AMGRAPH;
AMGRAPH A;//全局变量
AMGRAPH CreatGraph() //初始化
{
AMGRAPH G;
int i, j;
G.VEXNUM = 12; //14个顶点
G.ARCNUM = 16; //14条弧
for (i = 0; i<G.VEXNUM; i++)
G.VEXS[i].num = i; //第i个景点的编号为i
G.VEXS[0].name="26栋宿舍";
G.VEXS[1].name="二饭";
G.VEXS[2].name="泳池";
G.VEXS[3].name="网球场";
G.VEXS[4].name="沙地";
G.VEXS[5].name="旧场";
G.VEXS[6].name="新场";
G.VEXS[7].name="明德楼";
G.VEXS[8].name="图书馆";
G.VEXS[9].name="弘毅楼";
G.VEXS[10].name="天佑楼";
G.VEXS[11].name="艺悦楼";
G.VEXS[0].introduction="26栋宿舍位于学子路西侧,是计算机学院学生所住宿舍,万通超市上方。";
G.VEXS[1].introduction="第二学生饭堂位于学子路东侧,是学生好评最多的食堂。";
G.VEXS[2].introduction="北理工泳池位于学校后山半山腰上,对学生及社会人士都开放。";
G.VEXS[3].introduction="网球场位于学校东门附近,有4个场地供学生打网球。";
G.VEXS[4].introduction="沙地位于网球场西侧,以往学生在此举办各种活动,是一处聚会场地。";
G.VEXS[5].introduction="旧场位于网球场北侧,是北理珠最早的篮球场。";
G.VEXS[6].introduction="新场位于沙地西侧,是较新的篮球场。";
G.VEXS[7].introduction="明德楼位于学校中部,在夺命坡上方,是主要教学楼之一。";
G.VEXS[8].introduction="图书馆位于学校北门一侧,集图书馆、办公室、酒店于一体。";
G.VEXS[9].introduction="弘毅楼位于学校新大门对面,是主要教学楼之一。";
G.VEXS[10].introduction="天佑楼位于弘毅楼西侧,是航空学院的主教学楼。";
G.VEXS[11].introduction="艺悦楼位于天佑楼西侧,是设计与艺术学院的主教学楼。";
for (i = 0; i<G.VEXNUM; i++)
for (j = 0; j<G.VEXNUM; j++)
G.ARCS[i][j].length = MAXINT;
G.ARCS[0][1].length=20;
G.ARCS[0][2].length=100;
G.ARCS[0][3].length=280;
G.ARCS[1][3].length=280;
G.ARCS[1][4].length=110;
G.ARCS[1][7].length=210;
G.ARCS[2][7].length=130;
G.ARCS[1][9].length=280;
G.ARCS[3][4].length=20;
G.ARCS[3][5].length=5;
G.ARCS[4][6].length=5;
G.ARCS[5][8].length=35;
G.ARCS[6][8].length=50;
G.ARCS[7][9].length=80;
G.ARCS[8][9].length=200;
G.ARCS[9][10].length=40;
G.ARCS[10][11].length=20;
for (i=0;i<G.VEXNUM;i++)
for (j=0;j<G.VEXNUM;j++)
G.ARCS[j][i].length = G.ARCS[i][j].length; //无向网
return G;
}
void SHORTESTPATH_DIJ(AMGRAPH *G)
{//DIJ算法,计算最短路径
int V,min,i,j,w,k=0,V0,f=1,t;
int D[32],PATH[32][32];
bool S[32];
while (f)
{
cout<<"请输入一个起始景点编号:";
cin>>V0; //输入一个值赋给V0
if (V0<0 || V0>G->VEXNUM)
{
cout<<"景点编号不存在!请重新输入景点编号:";
cin>>V0;
}
if (V0 >=0 && V0<G->VEXNUM)
f=0;
}
for(V=0;V<G->VEXNUM;V++)
{
S[V]=false;
D[V]=G->ARCS[V0][V].length;
for(w=0;w<G->VEXNUM;w++)
{
PATH[V][w]=0;
}
if(D[V]<MAXINT)
{
PATH[V][V0]=1;
PATH[V][V]=1;
}
}
D[V0]=0;
S[V0]=true;
for(i=1;i<G->VEXNUM;i++)
{
min=MAXINT;
for(w=0;w<G->VEXNUM;w++)
{
if(!S[w]&&D[w]<min)
{
V=w;
min=D[w];
}
}
S[V]=true;
for(w=0;w<G->VEXNUM;w++)
{
if(!S[w] && (min+G->ARCS[V][w].length<D[w]))
{
D[w]=min+G->ARCS[V][w].length;
for(j=0;j<G->VEXNUM;j++)
PATH[w][j]=PATH[V][j];
PATH[w][w]=1;
}
}
}
for(V=0;V<G->VEXNUM;V++)
{
t=0;
if(V0!=V)
printf("%s",G->VEXS[V0].name);
for(w=0;w<G->VEXNUM;w++)
{
if(PATH[V][w]!=0 && w!=V0)
{
printf("-%s",G->VEXS[w].name);
if(w==5||w==6)
{
t=1;
}
}
k++;
}
if(V0!=V&&(V0==5||V0==6||t==1))
{
cout<<"\t此路段部分需步行!";
t=0;
}
if(k>G->VEXNUM-1 && V0!=V)
printf("\t路程:%dm\n\n",D[V]);
}
}
void SHORTESTPATH_FLOYD(AMGRAPH G)
{//FLOYD算法计算各对顶点之间的最短路径
int D[32][32],PATH[32][32];
int i,j,k;
for(i=0;i<G.VEXNUM;i++)
for(j=0;j<G.VEXNUM;i++)
{
D[i][j]=G.ARCS[i][j].length;
if(D[i][j]<MAXINT) PATH[i][j]=i;
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++)
{
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j]=D[i][k]+D[k][j];
PATH[i][j]=PATH[k][j];
}
}
}
void printjuzhen(AMGRAPH G)
{
int i,j,W=0;
cout<<"图的邻接矩阵:"<<endl;
for(i=0;i<G.VEXNUM;i++)
{
for(j=0;j<G.VEXNUM;j++)
{
if(G.ARCS[i][j].length==MAXINT)
{
cout<<setw(6)<<"∞";
}
else
cout<<setw(6)<<G.ARCS[i][j].length;
W++;
if(W%G.VEXNUM==0)
cout<<endl;
}
}
}
void main()
{
A=CreatGraph();
SHORTESTPATH_DIJ(&A);
printjuzhen(A);
}
请问怎么可以正确地打印最近的路,而不是按照地点的数字顺序打印出错误的线路。