h

#include<stdio.h>
#include<string.h>
#define MAXVEX 20
#define INFINITY 32768

typedef struct
{
int num;//地点序号
char name[20];//地点名称
}Vextype;//顶点类型

typedef struct
{
int arcs[MAXVEX][MAXVEX];//边集
Vextype vex[MAXVEX];//顶点集
int vexnum;//顶点数目
int arcnum;//边数目
}AdjMatrix;//邻接矩阵

//根据城市名称确定城市序号
int Locate(AdjMatrix *G,char name[])
{
int i;
for(i=1;i<=G->vexnum;i++)
if(!strcmp(name,G->vex[i].name))
return i;
return -1;
}

//采用邻接矩阵创建无向图
int Create(AdjMatrix *G)
{
int i,j,k,weight;
char site[20];
printf("请输入校园平面图中的地点数目和路线数目(sitenum,cutnum):\n");
scanf("%d,%d",&G->vexnum,&G->arcnum);
for(i=1;i<=G->vexnum;i++)
for(j=1;j<=G->vexnum;j++)
G->arcs[i][j]=INFINITY;
printf("请输入校园平面图中的%d个地点:\n",G->vexnum);
for(i=1;i<=G->vexnum;i++)
{
printf("num.%d个地点:",i);
G->vex[i].num=i;
flushall();
scanf("%s",G->vex[i].name);
}
printf("请输入校园平面图中的%d条路线:\n",G->arcnum);
for(k=0;k<G->arcnum;k++)
{
printf("num.%d条路线:",k+1);
printf("\n起点地点:");
scanf("%s",site);
i=Locate(G,site);
printf("终点地点:");
scanf("%s",site);
j=Locate(G,site);
printf("公里数:");
scanf("%d",&weight);
G->arcs[i][j]=weight;
G->arcs[j][i]=weight;//如果是有向图，就删掉此句
}
return (1);
}

//显示图信息
void Display(AdjMatrix *G)
{
int i,j;
printf("\n地点相关信息:\n");
for(i=1;i<=G->vexnum;i++)
{
for(j=1;j<=i;j++)
{
if(G->arcs[i][j]!=INFINITY)
printf("%s<--->%s:%6dkm\n",G->vex[j].name,G->arcs[i][j]);
}
}
}

void Serach(AdjMatrix *G)
{
char site[20];
int num,i,j;
printf("请输入要查询的地点:");
scanf("%s",site);
num=Locate(G,site);
printf("地点相关信息为:\n");
for(i=1;i<=G->vexnum;i++)
if(i==num)
for(j=1;j<=G->vexnum;j++)
if(G->arcs[i][j]!=INFINITY)
printf("%s---%s:%dkm\n",G->vex[num].name,G->vex[j].name,G->arcs[i][j]);
}

//增加新路线
void Add(AdjMatrix *G)
{
char site[20];
int start,end,weight;
printf("请输入增加路线的起点地点:");
scanf("%s",site);
start=Locate(G,site);
printf("终点地点:");
scanf("%s",site);
end=Locate(G,site);
printf("距离:");
scanf("%d",&weight);
G->arcs[start][end]=weight;
G->arcs[end][start]=weight;
}

//撤销新路线
void Add(AdjMatrix *G)
{
char site[20];
int start,end;
printf("请输入撤销路线的起点地点:");
scanf("%s",site);
start=Locate(G,site);
printf("终点地点:");
scanf("%s",site);
end=Locate(G,site);
G->arcs[start][end]=INFINITY;
G->arcs[end][start]=INFINITY;
}

//采用Dijkstra算法求得从起点地点到各终点地点的最短路线
void Dijkstr