课程设计（论文）-最短路径课程设计报告.docx

最短路径问题课程设计报告设计题目： 最短路径问题 专业： 学号： 姓名： 指导教师： 目录一、摘要2二、功能分析2三、需求分析2四、总体设计2五、具体实现21、具体代码及说明22、过程说明：63、运行结果：6六、总结8一、 摘要本单元设计主要解决设计一个程序，用户输入起始位置，就能得到该点到其他点的最短路线，及最短距离。在程序设计中,采用了C面向对象编程语言，采用控制台界面，将功能分模块实现，对问题中的要求做出了准确的实现。程序通过调试运行，实现了设计目标。 关键词：C、控制台界面、弗洛伊德（Floyd）二、 功能分析在一个网络中，如果两个结点之间有直接的因果关系，则这两个结点直接连通，在连接两个结点的弧上标上它的代价或权，给出两个结点求这样一条最短的路径，使经过这条路径上的代价之和最小，这就是最短路径问题。本题运用Floyd算法。三、 需求分析最短路径算法在生活中的应用相当广泛，生活中经常出现，如 乘公交，、交巡警服务平台的设置与调度等。四、 总体设计根据课设题目要求，拟将整体程序分为四大模块。每个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面子模块。以下是四个模块的大体分析： 1. 利用文件读入表示各顶点信息的邻近矩阵。 2. 应用Floyd算法求出所给图的距离矩阵和最短路径矩阵。 3. 通过求出的所给图的距离矩阵和最短路径矩阵，输出最短路径。4. 在主函数中调用上面三个子函数，完成求最短路径的程序设计。 五、 具体实现1、具体代码及说明#include#define max 20/输入邻接矩阵和点数/以形参的形式返回路径长度及其路径矩阵/因为直接传二维数组不能改变原值，所以需要传二级指针/n个点int zdlj(int (*a)max,int n,int (*sp)max,int (*path)max)/不要0行0列int i,j,m;/int bmaxmax=0;/保存路径长度/sp=a; /shortpath /错了，应该为赋值，而不是赋地址for(i=0;in;i+)for(j=0;jn;j+)spij=aij;/保存路径，/第i行表示第i个节点到其他节点时需要经过的节点/第j列表示其他节点到第j个节点时需要经过的节点/path=b; /错了i=j=m=0;for(i=0;in;i+)for(j=0;jn;j+)pathij=j;for(m=0;mn;m+)for(i=0;in;i+)for(j=0;jspim+spmj)spij=spim+spmj;pathij=pathim; return 0;/利用文件读入矩阵int drjz(int (*a)max,int n) FILE *fp; int mmaxmax; int i,j; if(fp=fopen(jz.txt,r)=NULL) printf(cant open file!); getchar(); exit(0); for(i=0;in;i+) for(j=0;jn;j+) fscanf(fp,%d,&aij); fclose(fp); /把三角矩阵变成对称矩阵 for(i=0;in;i+) for(j=0;j,x); while(1) /printf(%d-,pathxy); if(pathxy!=y) printf(%d-,pathxy); x=pathxy; else printf(%d,pathxy); break; return 0;int main()int amaxmax;int n,spmaxmax=0,pathmaxmax=0;int i,j,x,y;n=17; / drjz(a,n); printf(邻接矩阵为：n);for(i=0;in;i+)for(j=0;jn;j+)printf(%3d,aij);printf(n);zdlj(a,n,sp,path); printf(距离矩阵为：n); for(i=0;in;i+)for(j=0;jn;j+)printf(%2d,spij);printf(n); printf(路径矩阵为：n); for(i=0;in;i+)for(j=0;jn;j+)printf(%2d,pathij);printf(n); printf(输入要查找的两个顶点标号：n); scanf(%d%d,&x,&y); sc(sp,path,x,y);getchar(); getchar();return 0;2、过程说明：path矩阵第1行，第6列的值为6，表示从第1点到第6点的最短路径为6。R矩阵第1行第6列的值为2，第2行第6列的值为5，而第5行第6列的值为6，因此，16的最短路线为：1256。path矩阵第3行，第4列的值为5，表示从第3点到第4点的最短路径为5。R矩阵第3行第4列的值为2，第2行第4列的值为4，因此，34的最短路线为：324。3、运行结果：六、 总结课程设计总结： 本次课程设计涉及到的范围很广，让我能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。 1. 又一次复习了C语言，在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用BCB的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用。 2. 对数据结构的理解有待加强，这次课程设计应用的算法是Floyd算法。在学习的过程中自己就对这方面的知识比较生疏，所以刚拿到这个课设题目时，自己还是有些不自信，好在自己没有气馁，一步一步的努力终于取得了成功。 3. 此次设计让我意识到程序设计要求我们必须有不放弃的精神，不能因为几个错误就轻言放弃，只有坚持不懈方能取得成功。 4. 此次课程设计时间虽短，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有