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;
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;iD[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 %s",G.vexs[k].city); //打印路径顶点
k=P[k][w]; //获得下一个路径顶点下标
}
printf(" -> %sn",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(" -> %sn",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
六、运行结果及分析
1、建立城市图（经检验，图已建成，城市信息已存储）
2、显示每个城市对应编号以及邻接矩阵
3、求城市的最短距离
（1）求一个城市到所有城市的最短距离
当输入城市不存在时，会提示该城市不存在！请重新输入！直至输入存在的城市。
（2）求任意的两个城市之间的最短距离
1.当输入城市不存在时，会提示该城市不存在！请重新输入！直至输入存在的城市
2.当输入的起点城市和终点城市之间不存在路线时，输出不存在路线！
4、添加新的城市
经验证，新城市已经添加成功。
5、删除已有城市
经验证，城市已被删除成功。
6、编辑已有城市
经验证，编辑城市成功。
7、退出城市交通咨询系统
