《数据结构课程设计》最短路径问题实验报告(3)

实例2运行结果：

10

六、总结与心得

该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心的各种问题（当然此次试验最终主要解决的问题是：最短路径问题）。

这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。

经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉算法、弗洛伊德算法等，对树的学习有了一个更深的了解。

参考文献

【1】《数据结构》严蔚敏.清华大学出版社. 【2】《数据结构课程设计》苏仕华.极械工业出版社.

11

附录

#include #include #define MVNum 100 #define Maxint 32767

enum boolean{FALSE,TRUE}; typedef char VertexType; typedef int Adjmatrix; typedef struct{ VertexType vexs[MVNum]; Adjmatrix arcs[MVNum][MVNum]; }MGraph;

int D1[MVNum],p1[MVNum];

int D[MVNum][MVNum],p[MVNum][MVNum]; void CreateMGraph(MGraph * G,int n,int e) { int i,j,k,w; for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint; printf(\输入%d条边的i.j及w:\\n\ for(k=1;k<=e;k++){ scanf(\ G->arcs[i][j]=w; } printf(\有向图的存储结构建立完毕！\\n\}

void Dijkstra(MGraph *G,int v1,int n) { int D2[MVNum],p2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++){ S[v]=FALSE; D2[v]=G->arcs[v1][v]; if(D2[v]

12

p2[v]=0; } D2[v1]=0; S[v1]=TRUE; for(i=2;iarcs[v][w]arcs[v][w]; p2[w]=v; } } printf(\路径长度 路径\\n\ for(i=1;i<=n;i++){ printf(\ printf(\ while(v!=0){ printf(\ v=p2[v]; } printf(\ } }

void Floyd(MGraph *G,int n) { int i,j,k,v,w; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if( G->arcs[i][j]!=Maxint) p[i][j]=j; else p[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]

13

D[i][j]=D[i][k]+D[k][j]; p[i][j]=p[i][k]; } } } }

void main() { MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph)); printf(\输入图中顶点个数和边数n,e:\ scanf(\ CreateMGraph(G,n,e); while(xz!=0){ printf(\求城市之间最短路径************\\n\ printf(\ printf(\求一个城市到所有城市的最短路径\\n\ printf(\求任意的两个城市之间的最短路径\\n\ printf(\ printf(\请选择 :1或2，选择0退出:\\n\ scanf(\ if (xz==2){ Floyd(G,n); printf(\输入源点（或起点）和终点:v,w:\ scanf(\ k=p[v][w]; if (k==0) printf(\顶点%d 到 %d 无路径!\\n\ else { printf(\从顶点%d 到 %d 最短路径路径是:%d\ while (k!=w){ printf(\ k=p[k][w]; } printf(\ printf(\径路长度:%d\\n\ } } else if(xz==1) printf(\求单源路径，输入源点v :\

14

}

scanf(\ Dijkstra(G,v,n); }

printf(\结束求最短路径，再见!\\n\

15