C语言设计无向带权图表示最短路径及实验报告
1、源程序的展示：
#include<stdio.h>
#include<stdlib.h>
#define MVNum 100 //用于数组中
#define Maxint 9999 /*将无穷大的数值设为9999*/
typedef char vertextype;/*建立无向图*/
typedef int adjmatrix;
typedef struct
{ vertextype vexs[MVNum];
adjmatrix arcs[MVNum][MVNum];
}mgraph;
mgraph *G[2]; //设置指针数组用以实现最短路径
void city_number() //输出景点代表序号以及景点内容
{
printf("*************************************************************************\n");
printf("1、一号楼 2、三号公寓楼 3、沁园 4、旧饭堂 5、开水房 6、充话费营业厅 \n");
printf("7、行政楼 8、五号楼 9、体育馆 10、七桥 \n");
printf("*************************************************************************\n");
printf("1、 信息工程学院系楼： 专业有 计算机科学与技术 物联网 信息管理\n");
printf("2、信息工程学院女学生住宿楼： 计算机科学与技术 物联网 信息管理 \n");
printf("*************************************************************************\n");
printf("3、 沁园： 校园景点 有：柳树环绕的人工湖 假山瀑布 \n");
printf("4、 旧饭堂： 学校的一个饭堂之一，分为两层 \n");
printf("*************************************************************************\n");
printf("5、 开水房： 打水的地方 ，一壶水0.15元 \n");
printf("6、 充话费： 旧饭堂下面有一个，其他的在打水放旁边 \n");
printf("*************************************************************************\n");
printf("7、 行政楼： 学校的办公楼，是学校的管理枢纽 \n");
printf("8、 五号路： 大多数的课都在这里上课，是学校最热闹的地方\n");
printf("*************************************************************************\n");
printf("9、 体育馆： 大家放松的地方，有篮球、羽毛球等场地 \n");
printf("10、 七桥园： 这是一个以众所周知的题为主题的景点 \n");
printf("\n************************************************************************n");
}
void Createmgraph(int a,int n,int e)/*建立无向邻接矩阵*/
{
int i,j,k;
int w;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
G[a]->arcs[i][j]=0;/*邻接矩阵对角线初始值设为0*/
else G[a]->arcs[i][j]=Maxint;/*其他元素设为无穷大*/
for(k=1;k<=e;k++)/*读入e条边数的信息*/
{
printf("\n输入图中各起点终点及其权值i,j,w:");/*读入无向边及其权值*/
scanf("%d,%d,%d",&i,&j,&w);
G[a]->arcs[i][j]=w;
G[a]->arcs[j][i]=w;
}
}
void Dijkstra(int a,int v0,int N)/*Dijkstra（迪杰斯特拉）算法的实现和打印*/
{
enum boolean S[MVNum];/*终点集合*/
int dist[MVNum],path[MVNum];/*dist表示源点v0到图中其余顶点的最短长度，path表示其对应的路径*/
int i,wmin,u,num=1,k;
for(i=1;i<=N;i++)/*数组dist和集合S付初值*/
{
dist[i]=G[a]->arcs[v0][i];/*数组dist初值为邻接矩阵*/
S[i]=0;/*集合S初值设为空集*/
if(dist[i]<Maxint)
path[i]=v0;
else path[i]=0;
}
S[v0]=1;/*源点v0放入集合S中*/
path[v0]=0;
do{wmin=Maxint;/*wmin最小值设为无穷大*/
u=v0;
for(i=1;i<=N;i++)
if(S[i]==0)/*选择不在S中且距离最小的顶点u*/
if((dist[i]<wmin)&&(dist[i]!=0))
{
u=i;
wmin=dist[i];
}
S[u]=1;/*把距离最小的顶点u放入集合S中*/
for(i=1;i<=N;i++)/*修改不在S中的顶点距离*/
if(S[i]==0)
if(dist[u]+G[a]->arcs[u][i]<dist[i])
{
dist[i]=dist[u]+G[a]->arcs[u][i];
path[i]=u;
}
num++;
}
while(num<=N);
printf("\n\t输出带权无向图的单元最短路径为:\n\t");/*打印v0到其他顶点的最短路径*/
for(i=1;i<=N;i++)
{
if(S[i]==1)
{
k=i;
printf("\n\t顶点%d到%d之间的路径为:",v0,i);
while(k!=v0)
{
printf("%d<--",k);/*输出后继顶点*/
k=path[k];/*继续寻找下一个后继顶点*/
}
printf("%d",k);/*输出终点*/
printf(",最短路径长度为%d\n",dist[i]);/*输出最短路径*/
}
else printf("\n\t顶点%d到%d之间没有路径！",v0,i);
}
printf("\n\t求一个城市到所有城市的最短路径结束，谢谢！\n\n\t\t");
}
void main()/*旅游咨询系统*/
{
int n,e,v,u,i,x;
int z=0;
G[1]=(mgraph *)malloc(sizeof(mgraph));/*建立类型为mgraph的十字链表结构*/
G[2]=(mgraph *)malloc(sizeof(mgraph));
printf("****************欢迎使用旅游咨询系统****************\n");
printf("输入图中顶点个数和边数n,e:");
scanf("%d,%d",&n,&e);
city_number();
for(i=1;i<=n;i++)/*输入顶点信息*/
{
printf("\n请输入图的所有顶点i=");
scanf("%d",&x);
G[1]->vexs[i]=x;/*将顶点信息输入一维数组中*/
G[2]->vexs[i]=x;
}
printf("\n请输入距离矩阵的数值\n");
Createmgraph(1,n,e);/*建立距离矩阵*/
printf("\n无向图的存储结构建立完毕！\n");
do{
printf("\n\n\n************进行最短查询************\n");
printf("=========================================\n");
printf("1.求一个景点到所有景点的最短路径\n");
printf("2.退出\n");
printf("=========================================\n");
printf("请输入选择:");
scanf("%d",&z);/*输入选择的操作*/
city_number();
if(z==1)
{
printf("\n求一个景点到其他景点的最短路径:\n");
printf("求单源路径,输入源点v为:");/*输入源点v0*/
scanf("%d",&v);
Dijkstra(1,v,n);//计算最短距离（迪杰斯特拉）
}
else if(z==2)
printf("\n结束查询!谢谢使用!!\n");
else printf("输入错误!!\n");/*输入不为1-3则重新选择*/
}while(z!=2);/*输入2则退出*/
printf("谢谢您的使用,再见!!!!\n");
}
2、一、【问题描述】
1) 从校园的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。
本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息
3、二、【任务要求】
1) 从校园的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。
2) 为来访客人提供图中任意景点相关信息的查询。
3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
4、三、程序的大概结构
校园导游咨询与最短路径
1》输入景点的名称和内容；
2》建立无向有权图；
3》迪杰斯特拉求最短路径；
4》退出。
5、四
#include<stdio.h>
#include<stdlib.h>
#define MVNum 100 //用于数组中
#define Maxint 9999 /*将无穷大的数值设为9999*/
~~
~~
~~
printf("谢谢您的使用,再见!!!!\n");
}
6、五、课程设计总结
写程序解决最短路程问题，我首先查阅了数据结构，对Dijkstra方法有了一定的了解，会针对某一具体的图，运用这种方法求解某一点到其余各个点的最短路程，在运用Dijkstra方法编写代码求解最短路径的时候我遇到了很多困难。但是最终都得到解决，这次程序设计让我对数据结构有了更深的认识，对程序的编写有了一定的信心！
