一、实验目的
????????1）熟悉并掌握图的存储结构；
????????2）熟悉并掌握单个最短路径算法；
????????3）熟悉并掌握任意两个顶点之间的最短路径算法。
二、实验内容
????????设计一个交通咨询系统，能让乘客咨询从一个城市顶点到另一个城市顶点之间的最短路径或者最低费用或最少时间等问题。对于不同咨询需求，可以输入城市间的路程或所需要时间或费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。
要求：
????????1）构建城市信息有向图，可以以城市名为节点名，城市之间采用交通工具的时间或费用为边的权值进行构建；
????????2）可以在已构建的城市信息图中添加新的城市、删除已有城市或编辑已有城市及其相关的边；
????????3）给出从一个城市到其他各个城市所花费的最短时间或最低费用；
????????4）提供一种最快或最省钱的方式到达；如输入两个城市名，给出从一个城市到另一个城市的最短时间或最低费用。
三、实验步骤
????????1）定义图的存储方式；
????????2）构建图；?
????????3）定义main函数，并列出菜单：包括添加一个城市；删除一个城市；编辑一个城市；一个城市到其他城市之间的最短路径；任意两个城市之间的最短路径等
????????4）定义每个菜单的函数；
????????5）实现各个功能。
????????菜单类似于：
????????printf("******求城市之间的最短路径******\n");
???? ???printf("============================================\n");
? ? ? ? printf("1.求一个城市到所有城市的最短路径\n");
? ? ? ? printf("2.求任意的两个城市之间的最短路径\n");
? ? ? ? printf("3.添加新的城市\n");
? ? ? ? printf("4.删除已有的城市\n");
? ? ? ? printf("5.编辑已有的城市\n");
? ? ? ? printf("6.退出\n");
? ? ? ? printf("============================================\n");
? ? ? ? printf("请选择: 1 、2、3、4、5,6");
四、算法流程图
流程图1
?流程图2
流程图3?
?五、实现代码
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
#define N 100
int s;
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct Vextype{
char city[N];
int num;
};
typedef struct
{
Vextype vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}Mgraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
int zhuanhua(Mgraph g,char city[]){
int i,city1,k=0;
for (i=0;i<=g.numVertexes;i++){
if (strcmp(city,g.vexs[i].city)==0)
{
city1=g.vexs[i].num;
k=1;
}
}
return city1;
}
/* 构件图 */
void CreateMgraph(Mgraph &g)
{
int i, j;
char m[N],n[N];
int m1,n1;
printf("请输入城市数和路线数:");
scanf("%d%d",&g.numVertexes,&g.numEdges);
for (i=0;i<g.numVertexes; i++)//初始化图
{
g.vexs[i].num=i;
}
printf("请输入相对应的城市：\n");
for (i=0;i<g.numVertexes; i++)
{
printf("第%d个城市:",i+1);
scanf("%s",&g.vexs[i].city);
}
for (i=0;i<g.numVertexes;i++)/* 初始化图的邻接矩阵*/
{
for (j=i;j<g.numVertexes;j++)
{
if (i==j)
g.arc[i][j]=0;
else
g.arc[i][j]=g.arc[j][i]=INFINITY;
}
}
printf("\n");
printf("请输入%d条路径信息如下:\n",g.numEdges);
printf("起点城市 终点城市 路径长度\n");
for (i=0;i<g.numEdges;i++)
{
scanf("%s%s",&m,&n);
m1=zhuanhua(g,m);
n1=zhuanhua(g,n);
scanf("%d",&g.arc[m1][n1]);
}
}
int test(Mgraph g,char city[]){//测试输入的城市是否存在
int k=0;
for (int i=0;i<g.numVertexes;i++){
if (strcmp(g.vexs[i].city,city)==0){
k=1;
break;
}
}
return k;
}
/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(Mgraph G, Patharc &P, ShortPathTable &D)
{
int v,w,u,op;
char city1[N],city2[N];
int a,b,k,i;
for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */
{
for(w=0; w<G.numVertexes; ++w)
{
D[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */
P[v][w]=w; /* 初始化P */
}
}
for(u=0;u<G.numVertexes;++u)
{
for(v=0;v<G.numVertexes;++v)
{
for(w=0;w<G.numVertexes;++w)
{
if (D[v][w]>D[v][u]+D[u][w])
{//如果经过下标为k顶点路径比原两点间路径更短
D[v][w]=D[v][u]+D[u][w];//将当前两点间权值设为更小的一个
P[v][w]=P[v][u];//路径设置为经过下标为u的顶点
}
}
}
}
int s;
while (1){
printf("========================================\n");
printf("1.求一个城市到所有城市的最短路径\n");
printf("2.求任意的两个城市之间的最短路径\n");
printf("3.退出\n");
printf("========================================\n");
printf("请选择：");
scanf("%d",&op);
switch (op){
case 1:{
printf("请输入起点城市：");
scanf("%s",&city1);
while (1){
s=test(G,city1);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入起点城市：");
scanf("%s",&city1);
}
}
a=zhuanhua(G,city1);
printf("%s到各城市最短路径如下:\n",G.vexs[a].city);
for(w=0;w<G.numVertexes;w++)
{
if (D[a][w]!=INFINITY){
printf("%s - %s 最短路径为: %d ",G.vexs[a].city,G.vexs[w].city,D[a][w]);
k=P[a][w]; //获得第一个路径顶点下标
printf(" 路径为: %s",G.vexs[a].city); //打印源点
while(k!=w) //如果路径顶点下标不是终点
{
printf(" -> %s",G.vexs[k].city); //打印路径顶点
k=P[k][w]; //获得下一个路径顶点下标
}
printf(" -> %s\n",G.vexs[w].city); //打印终点
}
printf("\n");
}
break;
}
case 2:{
printf("请输入起点城市：");
scanf("%s",&city1);
while (1){
s=test(G,city1);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入起点城市：");
scanf("%s",&city1);
}
}
a=zhuanhua(G,city1);
printf("请输入终点城市：");
scanf("%s",&city2);
while (1){
s=test(G,city2);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入终点城市：");
scanf("%s",&city2);
}
}
b=zhuanhua(G,city2);
if (D[a][b]!=0&&D[a][b]!=INFINITY){
printf("%s - %s 最短路径为: %d ",G.vexs[a].city,G.vexs[b].city,D[a][b]);
k=P[a][b]; //获得第一个路径顶点下标
printf(" 路径为: %s",G.vexs[a].city); //打印源点
while(k!=b) //如果路径顶点下标不是终点
{
printf(" -> %s",G.vexs[k].city); //打印路径顶点
k=P[k][b]; //获得下一个路径顶点下标
}
printf(" -> %s\n",G.vexs[b].city); //打印终点
}
else
printf("%s到%s不存在路线！",G.vexs[a].city,G.vexs[b].city);
printf("\n");
break;
}
}
if (op==3) break;
}
}
void add(Mgraph &g){//添加新城市
int i,j,path,a,b,c;
int num,m1,n1;
char city1[N],city2[N];
char m[N],n[N];
g.numVertexes++;
b=g.numVertexes;
printf("请输入需要添加的新城市：");
scanf("%s",&g.vexs[b-1].city);
g.vexs[b-1].num=b-1;
printf("请输入需要添加的路线数：");
scanf("%d",&c);
g.numEdges=g.numEdges+c;
g.arc[b-1][b-1]=0;//初始化距离
for (int i=0;i<g.numVertexes-1;i++){
g.arc[i][b-1]=INFINITY;
g.arc[b-1][i]=INFINITY;
}
for (i=0;i<c;i++){
printf("请输入第%d个存在路线的城市：",i+1);
scanf("%s",&city2);
while (1){
s=test(g,city2);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入存在路线城市：");
scanf("%s",&city2);
}
}
printf("请输入城市之间距离:");
scanf("%d",&path);
a=zhuanhua(g,city2);
g.arc[b-1][a]=path;
printf("\n");
}
}
void Delete(Mgraph &g){//删除已有城市
int i,k=0;
int row,col;
char city[N];
printf("请输入要删除的城市：");
scanf("%s",&city);
while (1){
s=test(g,city);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入要删除的城市：");
scanf("%s",&city);
}
}
for (i=0;i<=g.numVertexes;i++){
if (strcmp(city,g.vexs[i].city)==0)
{
k=g.vexs[i].num;
break ;
}
}
for (i=k;i<g.numVertexes;i++){
g.vexs[i]=g.vexs[i+1];
}
g.numVertexes--;
for (i=0;i<g.numVertexes;i++){
g.vexs[i].num=i;
}
for (row=k;row<g.numVertexes;row++){
for (col=k;col<g.numVertexes;col++){
g.arc[row][col]=g.arc[row+1][col+1];
}
}
printf("城市%s已删除！\n",city);
}
void edit(Mgraph &g){//编辑已有城市
int i,k=0,path;
int a,b;
char city1[N],city2[N];
printf("请输入需要修改的城市：");
scanf("%s",&city1);
while (1){
s=test(g,city1);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入需要修改的城市：");
scanf("%s",&city1);
}
}
printf("请输入另外一个城市：");
scanf("%s",&city2);
while (1){
s=test(g,city2);
if (s==1) break;
else{
printf("该城市不存在！请重新输入！\n");
printf("请输入需要修改的城市：");
scanf("%s",&city2);
}
}
printf("城市距离：");
scanf("%d",&path);
a=zhuanhua(g,city1);
b=zhuanhua(g,city2);
g.arc[a][b]=path;
}
void output(Mgraph &g){//遍历所有城市，并输出每个城市信息
printf("城市编号\t城市\n");
for (int i=0;i<g.numVertexes;i++){
printf("%d\t\t%s\n",g.vexs[i].num,g.vexs[i].city);
}
printf("\n");
printf("构建的邻接矩阵如下所示.\n");
for(int i=0;i<g.numVertexes;i++)
{
for(int j=0;j<g.numVertexes;j++)
{
printf("%-8d ", g.arc[i][j]);
}
printf("\n");
}
}
int main()
{
int v,w,k,op;
Mgraph G;
Patharc P;
ShortPathTable D; /* 求某点到其余各点的最短路径 */
while(1){
printf("*********求城市之间的最短路径*********\n");
printf("===================================\n");
printf("\t1.建立城市图\n");
printf("\t2.显示每个城市信息\n");
printf("\t3.求城市的最短路径\n");
printf("\t4.添加新的城市\n");
printf("\t5.删除已有的城市\n");
printf("\t6.编辑已有的城市\n");
printf("\t7.退出\n");
printf("===================================\n");
printf("请选择：");
scanf("%d",&op);
switch (op){
case 1:{
CreateMgraph(G);
printf("城市图完成建立！\n\n");
break;
}
case 2:{
output(G);
printf("\n");
break;
}
case 3:{
ShortestPath_Floyd(G,P,D);
printf("\n");
break;
}
case 4:{
add(G);
printf("已成功添加新的城市！\n\n");
break;
}
case 5:{
Delete(G);
printf("\n");
break;
}
case 6:{
edit(G);
printf("已成功编辑城市！\n\n");
printf("\n");
break;
}
}
if (op==7) break;
}
return 0;
}
六、运行结果及分析
1、建立城市图（经检验，图已建成，城市信息已存储）?
?2、显示每个城市对应编号以及邻接矩阵
3、求城市的最短距离
?????? （1）求一个城市到所有城市的最短距离
????????????? 当输入城市不存在时，会提示该城市不存在！请重新输入！直至输入存在的城市。
（2）求任意的两个城市之间的最短距离
? ? ? ? 1.当输入城市不存在时，会提示该城市不存在！请重新输入！直至输入存在的城市
? ? ? ? 2.当输入的起点城市和终点城市之间不存在路线时，输出不存在路线！
?4、添加新的城市
?????????经验证，新城市已经添加成功。
5、删除已有城市?
????????经验证，城市已被删除成功。
6、编辑已有城市
?????????经验证，编辑城市成功。
7、退出城市交通咨询系统