实验八：校园交通咨询系统设计(最短路径).docx

实验八：校园交通咨询系统设计（最短路径）8.1 问题描述设计一个校内交通咨询系统，能让旅客咨询从任一教学楼到其余所有教学楼之间的最短路径，以及任意两幢教学楼之间的最短路径。校园内简图见图8-1，为通俗化程序，用数字序号代替楼的名称。 图8-18.2 输入与输出输入：输入图的顶点数，以及边数。输出：一幢楼到其他楼之间的最短路径，以及任意两幢楼之间的最短路径。8.3 需求分析1.建立交通网络图的存储结构。2.解决单源最短路径问题。3.最后实现两幢楼之间的最短路径。8.4 概要设计1.结构定义图的存储结构（邻接矩阵）#define MVNum 50 /*最大顶点数*/typedef int VertexType; typedef int Adjmatrix;typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum;MGraph;2.函数模块void CreateMGraph( MGraph *G, int n,int e)/*采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数*/void Dijkstra(MGraph *G, int v1,int n) /*迪杰斯特拉算法*/void Floyd(MGraph *G, int n) /*费洛伊德算法 */ 8.5 详细设计#include stdio.h#include stdlib.h#define MVNum 50 /*最大顶点数*/#define Maxvalue 32767enum boolean FALSE ,TRUE;typedef int VertexType; typedef int Adjmatrix;typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum, path1MVNum;/D都是表示路径长度，p都是表示路径经过的顶点。源点到所有顶点int DMVNumMVNum, pathMVNumMVNum;/任意两个顶点之间的最短路径void CreateMGraph( MGraph *G, int n,int e);void Dijkstra(MGraph *G, int v1,int n) ;void Floyd(MGraph *G, int n);void main() MGraph *G; int n,e,v,w,k; int choice= 1; G=(MGraph *)malloc(sizeof(MGraph); printf(n请输入图中顶点的个数和边数 n，e：n); scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);/*建立图的存储结构*/printf(*计算校园内教学楼之间的最短路径*n);printf(n*n);printf(1.求一幢教学楼到所有教学楼的最短路径n);printf(2.求任意两幢教学楼之间的最短路径n);printf(0.退出程序n);printf(*n);printf(请输入您的选择：1 or 2 or 0 .n);while(choice!=0) /*可以改为choice，把结构换成switch choice结构*/scanf(%d,&choice);switch(choice)case 2: Floyd(G,n); /*调用费洛尹德函数*/ printf(输入源点和终点：v，w：); scanf(%d,%d,&v,&w); k=pathvw; /*k为起点v的后继顶点*/ if(k=0) printf(顶点%d 到%d无路径！n,v,w); else printf(从顶点%d到%d的最短路径是：%d,v,w,v); while(k!=w ) printf(-%d,k);/*输出后继顶点*/ k=pathkw; printf(-%d,w); printf(路径长度:%dn,Dvw);printf(请输入您的选择：1 or 2 or 0 .n);break;case 1: printf(求单源路径，输入源点v：); scanf(%d,&v); Dijkstra(G,v,n); printf(请输入您的选择：1 or 2 or 0 .n);break;default: printf(结束求最短路径，再见！n);/*输入所有有向边及其权值,建立有向图的存储结构*/void CreateMGraph( MGraph *G, int n,int e)/*采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数*/ int i,j ,k,w; for(i=1;ivexsi=i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxvalue; /*初始化邻接矩阵 应该是32767*/printf(输入%d条边的i，j及w:n,e);for(k=1;karcsij=w;printf(图的存储结构建立完毕nn);void Dijkstra(MGraph *G, int v1,int n) /*地杰斯特拉算法c语言描述*/ /*用地杰斯特拉算法求有向图G的v1顶点到其他顶点的最短路径Pv及其权DV设G是有向图的邻接矩阵，若边 不存在，则Gij=Maxintsv为真当且仅当v属于s，即已求得从v1到v的最短路径*/int D2MVNum,path2MVNum;int v,i,w,min;enum boolean sMVNum;for(v=1;varcsv1v;/*置初始的最短路径值*/if(D2vMaxvalue) path2v=v1;/*v1是v的前驱*/else path2v=0;/*v无前驱*/D2v1=0;sv1=TRUE;/*s集初始时只有源点，源点到源点的距离为0开始循环，每次求得v1到某个v顶点的最短路径，并加v到s集中*/for(i=2;i=n;i+)/*其余n-1个顶点*/min=Maxvalue;for(w=1;w=n;w+) if(!sw&D2wmin) v=w;min=D2w;/*w顶点离v1顶点更近*/ sv=TRUE; for(w=1;warcsvwarcsvw; path2w=v;printf(路径长度 路径n);for(i=1;i=n;i+)printf(%6d,D2i); printf(%13d,i); v=path2i;while(v!=0)printf(-%d,v);v=path2v;printf(n);/*非罗伊德算法*/void Floyd(MGraph *G, int n) int i,j,k,v,w; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxvalue) pathij=j;/* j是i的后继*/ else pathij=0; Di