西工大数据结构实验报告 最短路径和最小花费

1、最短路径和最小花费实验报告一实验题目求给定图中的最短路径。二程序设计(一) 需求分析本题需要建立这样一个程序，对于给定的图，包含地点，路径，方向和长度权值和路费权值。输入任意两个结点，能够求出两个地点之间的最短路程和路径，最少路费及路径。（二）概要设计1程序模块及思想：1.主函数主函数的中心思想如下：（1）开始；（2）按照字典序，输出城市编号；（3）选择要进行的操作：（1）输出两地间的最短路程和路径；（2）输出两地间的最少路费及路径；（4）若选择1：（1）则按照已知的信息：城市，已知路径，长度权值，建立一个图；（2）输入起点和终点；（3）按照弗洛伊德算法求得最短路程和路径；（4）输出。若选择2

2、：（1）则按照已知的信息：城市，已知路径，路费权值，建立一个图；（2）输入起点和终点；（3）按照弗洛伊德算法求得最少路费和路径；（4）输出。（5）结束。2基本操作和基本定义（1）基本定义typedef char VertexType; /定义定点数组typedef int Adjmatrix; /定义稀疏矩阵 typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，类型假定为int型 MGraph;（2）基本操作void CreateMGraph(MGraph *G,int n,

3、int e,int *A)操作结果：创建图，以邻接矩阵形式储存。void Floyd(MGraph *G,int n)操作结果：找到图中的最短路径。（三）详细设计1结构体定义typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，类型假定为int型 MGraph;作用：定义图的结构体2.每个模块的分析：（1）主函数：void main() MGraph *G; int v,w,k,K,i=0;int xz=1; G=(MGraph *)malloc(sizeof(MGraph);

4、 /初始化printf("各城市的编号如下：n"); for(i=0;i<22;i+) printf("%s ",cityi); printf("n"); /输出城市列表及编号while(xz!=0) printf("1.求一个城市到另一个城市的最少路费:n"); printf("2.求任意两个城市间的最短路径:n"); scanf("%d",&xz); if(xz=2) /求最短路程及路径 CreateMGraph(G,22,52,(int*)A); Floy

5、d(G,22); printf("输入起点和终点的编号:n"); scanf("%d%d",&v,&w); k=Pvw; / P为路径中的结点。 if(k=0) printf("起点%d到终点%d无路径n",v,w); else printf("从起点%d到%d的最短路径是:%d",v,w,v); while(k!=w) printf("->%d",k); k=Pkw;/输出结点 printf("->%d",w); printf("路径长

6、度为:%dn",Dvw); printf("n"); else if(xz=1) /求最少路费及路径 CreateMGraph(G,22,52,(int*)a); Floyd(G,22); printf("输入起点和重点的编号：n"); scanf("%d%d",&v,&w); k=Pvw; K=Pvw; if(k=0) printf("起点%d到终点%d无路径,",v,w); printf("即%s到%s无路径n",Cityv-1,Cityw-1); else /依次

7、输出最省钱路径上的节点 printf("从起点%d到%d的最省钱路径是:%d",v,w,v); while(k!=w) printf("->%d",k); k=Pkw; printf("->%dn",w); printf("即从%s到%s的最省钱路径是:%s",Cityv-1,Cityw-1,Cityv-1); while(K!=w) printf("->%s",CityK-1); K=PKw; printf("->%sn",CityK-1); pri

8、ntf("最少花费为:%dn",Dvw); printf("n"); printf("输入0结束n"); /结束（2）基本操作函数（1）创建一个图的函数void CreateMGraph(MGraph *G,int n,int e,int *A) /采用邻接矩阵表示法构造有向图G,n和e表示图的顶点数和边数 int i,j,k,w; for(i=1;i<=n;i+) G->vexsi=(char)i;for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint; /

9、初始化邻接矩阵 for(k=1;k<=e;k+) /由已知数组向邻接矩阵内，读入e条边，建立邻接矩阵 i=*(int*)A + 0*e + k-1); j=*(int*)A + 1*e + k-1); w=*(int*)A + 2*e + k-1); G->arcsij=w; printf("图建立完毕n"); （2）佛洛依德算法函数void Floyd(MGraph *G,int n) int i,j,k; for(i=1;i<=n;i+) /设置路径长度D和路径path初值 for(j=1;j<=n;j+) if(G->arcsij!=Ma

10、xint) Pij=j; /j是i的后继 else Pij=0; Dij=G->arcsij; for(k=1;k<=n;k+) /做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上 for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改长度 Pij=Pik; （3）其他intA352=1,1,1,2,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,8,9,11, 12,13,13,13,14,14,14,14,14,15,15,15,16,16,16,

11、16, 17,17,17,18,19,19,20,21,21,21,22,22,22, 4,6,9,19,1,6,15,22,13,14,20,16,1,4,14,8, 21,7,16,22,1,13,14,5,11,14,5,6,12,13,22,4,22,21, 5,8,17,18,16,18,19,16,17,2,17,5,4,7,15,8,14,15,700,200,800,700,700,800,350,900,1500,600,900,1100,200,800,300,900,1700,300,600,300,800,450,450,1500,450,1300,600,300,45

12、0,1300,100,350,300,850,1100,600,500,600,500,200,200,600,200,700,200,900,900,1700,850,300,1300,300;/二维数组的每一行分别为：起点，终点和路径权值。int a352=1,1,1,2,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,8,9,11, 12,13,13,13,14,14,14,14,14,15,15,15,16,16,16,16, 17,17,17,18,19,19,20,21,21,21,22,22,22, 4,6,9,19,1,6,15,22,13,14,20,16,1,4

13、,14,8, 21,7,16,22,1,13,14,5,11,14,5,6,12,13,22,4,22,21, 5,8,17,18,16,18,19,16,17,2,17,5,4,7,15,8,14,15, 45,125,45,55,75,35,45,35,45,15, 75,25,185,65,225,25,25,25,15,25, 45,75,110,15,55,10,35,135,110,100, 75,55,45,35,25,25,15,15,15,15, 15,25,15,55,35,75,35,25,25,45,75,45;/二维数组的每一行分别为：起点，终点和路费权值。(四) 程

14、序使用说明及测试结果程序运行截图如下:1. 求最短路径：2.求最少花费：三、实验总结(实验心得)1.你在编程过程中花时多少？ 答：从设计到编写，从调试到完成，直至最终完成实验报告一共用了约八个小时。2.多少时间在纸上设计？答：两个小时。3.多少时间上机输入和调试？答：四个多小时。4.多少时间在思考问题？答：设计前就思考，直至完成报告，十个小时。5.遇到了哪些难题？又是怎么克服的？答：在做这项作业时。我可以说自己遇到了无数难题，我的数据结构并不好图论的知识并不熟悉。因此完成这项作业的过程可谓艰辛。首先遇到的困难就是设计程序。去年C语言学得很不扎实，我对图的结构都不甚了解，更别说运用与之相关的算法

15、了。在设计程序之前：我花了很长时间复习书上与之相关的算法。由于知识的匮乏，我只能先将书上的图论有关的算法逐句逐句的分析， 然后在纸上设计相应的流程。最后凭借自己的知识，并利用同学的帮助，磕磕绊绊地编写了程序。接下来的困难，也就是最大，最麻烦，解决起来最耗费脑力，最枯燥乏味的问题调试程序。最初的程序编译之后，问题触目惊心，我根据系统的提示，首先补上了缺失的间隔符，又定义了遗漏的变量，再次编译，错误有所减少，但依然多，我又重新修改。接下来的错误越来越“高级”，数据类型，返回类型，函数类型等有关。我便循环往复，不厌其烦地修改，每当减少一个错误，我都会有几分高兴，而有的时候，修改后会产生更多

16、的错误。就这样一遍又一遍，终于系统显示没有错误和警告了。我运行了程序。当我按照自己的设想将输入数据时，敲下回车键后结果却令我傻了眼。屏幕上没有任何显示。，原来许多错误是编译器没有检测出来。最终通过我的调试，修改和同学的帮助，终于完成了程序。   6.你的收获有哪些？答：首先，我对稀疏矩阵和弗洛伊德算法的知识有了更多了解，破除了错误的认识。其次，通过这次作业，我掌握了图论有关的算法。最后，我还温习了有关C语言的许多知识，比如二维数组等。 参考文献：【1】严蔚敏数据结构第三章清华大学出版社附源代码：#include<stdio.h>#include<

17、stdlib.h> #include<string.h>#define MVNum 100 /最大顶点数 #define Maxint 99999typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，类型假定为int型 MGraph; int DMVNumMVNum,PMVNumMVNum; /*建立有向图的存储结构*/ void CreateMGraph(MGra

18、ph *G,int n,int e,int *A) /采用邻接矩阵表示法构造有向图G,n和e表示图的顶点数和边数 int i,j,k,w; for(i=1;i<=n;i+) G->vexsi=(char)i;for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint; /初始化邻接矩阵 for(k=1;k<=e;k+) /读入e条边，建立邻接矩阵 i=*(int*)A + 0*e + k-1); j=*(int*)A + 1*e + k-1); w=*(int*)A + 2*e + k-1); G->arcsi

19、j=w; printf("图建立完毕n"); /*迪杰斯特拉算法*/ /*弗洛伊德算法*/ void Floyd(MGraph *G,int n) int i,j,k; for(i=1;i<=n;i+) /设置路径长度D和路径path初值 for(j=1;j<=n;j+) if(G->arcsij!=Maxint) Pij=j; /j是i的后继 else Pij=0; Dij=G->arcsij; for(k=1;k<=n;k+) /做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上 for(i=1;i<=n;i+)

20、 for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改长度 Pij=Pik; int A352=1,1,1,2,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,8,9,11, 12,13,13,13,14,14,14,14,14,15,15,15,16,16,16,16, 17,17,17,18,19,19,20,21,21,21,22,22,22, 4,6,9,19,1,6,15,22,13,14,20,16,1,4,14,8, 21,7,16,22,1,13,14,5,11,14,5,6,12,13,22,4,22,21

21、, 5,8,17,18,16,18,19,16,17,2,17,5,4,7,15,8,14,15,700,200,800,700,700,800,350,900,1500,600,900,1100,200,800,300,900,1700,300,600,300,800,450,450,1500,450,1300,600,300,450,1300,100,350,300,850,1100,600,500,600,500,200,200,600,200,700,200,900,900,1700,850,300,1300,300;/第一行储存有向图的起点,第二行储存有向图的终点,第三行储存有向图的

22、权值，三者中各元素一一对应 int a352=1,1,1,2,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,8,9,11, 12,13,13,13,14,14,14,14,14,15,15,15,16,16,16,16, 17,17,17,18,19,19,20,21,21,21,22,22,22, 4,6,9,19,1,6,15,22,13,14,20,16,1,4,14,8, 21,7,16,22,1,13,14,5,11,14,5,6,12,13,22,4,22,21, 5,8,17,18,16,18,19,16,17,2,17,5,4,7,15,8,14,15, 45,1

23、25,45,55,75,35,45,35,45,15, 75,25,185,65,225,25,25,25,15,25, 45,75,110,15,55,10,35,135,110,100, 75,55,45,35,25,25,15,15,15,15, 15,25,15,55,35,75,35,25,25,45,75,45; char city2213="1.Amsterdam", "2.Athens", "3.Belfast","4.Berlin","5.Bern","6.Bruss

24、els", "7.Bucharest","8.Budapest", "9.Copenhagen", "10.Dublin","11.Lisbon", "12.London", "13.Madrid", "14.Paris", "15.Prague", "16.Sarajevo", "17.Skopja", "18.Sofia", "19.

25、Tirane", "20.Rome", "21.Vienna", "22.Warsaw" ; char City2213="Amsterdam", "Athens", "Belfast","Berlin","Bern","Brussels", "Bucharest","Budapest", "Copenhagen", "Dublin&qu

26、ot;,"Lisbon", "London", "Madrid", "Paris", "Prague", "Sarajevo", "Skopja", "Sofia", "Tirane", "Rome", "Vienna", "Warsaw" ;void main() MGraph *G; int v,w,k,K,i=0;int xz=1; G=(MGraph

27、 *)malloc(sizeof(MGraph); printf("各城市的编号如下：n"); for(i=0;i<22;i+) printf("%s ",cityi); printf("n");while(xz!=0) printf("1.求一个城市到另一个城市的最少路费:n"); printf("2.求任意两个城市间的最短路径:n"); scanf("%d",&xz); if(xz=2) /求最短路程和路径 CreateMGraph(G,22,52,(int

28、*)A); Floyd(G,22); printf("输入起点和终点的编号:n"); scanf("%d%d",&v,&w); k=Pvw; K=Pvw; if(k=0) printf("起点%d到终点%d无路径n",v,w); printf("即%s到%s无路径n",Cityv-1,Cityw-1); else printf("从起点%d到%d的最短路径是:%d",v,w,v); while(k!=w) printf("->%d",k); k=Pkw;

29、 printf("->%dn",w); printf("即从%s到%s的最省钱路径是:%s",Cityv-1,Cityw-1,Cityv-1); while(K!=w) printf("->%s",CityK-1); K=PKw; printf("->%sn",CityK-1); printf("路径长度为:%dn",Dvw); printf("n"); else if(xz=1) /求最少路费及路径 CreateMGraph(G,22,52,(int*)a

30、); Floyd(G,22); printf("输入起点和终点的编号：n"); scanf("%d%d",&v,&w); k=Pvw; K=Pvw; if(k=0) printf("起点%d到终点%d无路径,",v,w); printf("即%s到%s无路径n",Cityv-1,Cityw-1); else printf("从起点%d到%d的最省钱路径是:%d",v,w,v); while(k!=w) printf("->%d",k); k=Pkw; p

31、rintf("->%dn",w); printf("即从%s到%s的最省钱路径是:%s",Cityv-1,Cityw-1,Cityv-1); while(K!=w) printf("->%s",CityK-1); K=PKw; printf("->%sn",CityK-1); printf("最少花费为:%dn",Dvw); printf("n"); printf("输入0结束n"); /*两城市间的路费和距离起点 终点 路费 距离Ams

32、terdam Berlin 45 Amsterdam Brussels 125 Amsterdam Copenhagen 45 Athens Tirane 55 Berlin Amsterdam 75 Berlin Brussels 35 Berlin Prague 45 Berlin Warsaw 35Bern Madrid 45 Bern Paris 15 Bern Rome 75Bern Sarajevo 25Brussels Amsterdam 185 Brussels Berlin 65 Brussels Paris 225Bucharest Budapest 25Bucharest

33、 Warsaw 25 Budapest Bucharest 25 Budapest Sarajevo 15 Budapest Vienna 25Copenhagen Amsterdam 45 Lisbon Madrid 75 London Paris 110 Madrid Bern 15Madrid Lisbon 55 Madrid Paris 10 Paris Bern 35 Paris Brussels 135Paris London 110Paris Madrid 100 Paris Vienna 75Prague Berlin 55 Prague Vienna 45 Prague Warsaw 35 Sarajevo Bern 25 Sarajevo Budapest 25Sarajevo Skopja 15 Sarajevo Sofia 15Skopja Sarajevo 15Skopja Sofia 15Skopja Tirane 15Sofia Sarajevo 25 Sofia Skopja 15 Tirane Athens 55 Tirane Skopja 35 Rome Bern 75 Warsaw Berlin 35Warsaw Bucharest 25 Warsaw Prague 25 Vienna Budapest