C语言设计无向带权图表示最短路径及实验报告
1、源程序的展示：#include<stdio.h>#in罕铞泱殳clude<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>#defineMVNum100//用于数组中#defineMaxint9999/*将无穷大的数值设为9999*/~~~~~~ printf("谢谢您的使用,再见!!!!\n");}
6、五、课程设塥骈橄摆计总结写程序解决最短路程问题，我首先查阅了数据结构，对Dijkstra方法有了一定的了解，会针对某一具体的图，运用这种方法求解某一点到其余各个点的最短路程，在运用Dijkstra方法编写代码求解最短路径的时候我遇到了很多困难。但是最终都得到解决，这次程序设计让我对数据结构有了更深的认识，对程序的编写有了一定的信心！
