交通运输学院课程设计

《交通运输学院课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、交通运输学院课程设计目录第1章引言21.1目的：21.2内容：21.3主要任务：2第2章设计过程32.1设计思路32.1.1Floyd算法32.1.2邻接矩阵32.1.3图形用户界面42.2设计内容及分析42.2.1算法部分42.2.2图形界面处理部分：9第3章总结13附录14参考文献1714交通运输学院课程设计第1章引言1.1目的：发现课程学习中的不足和薄弱环节，予以补充和加强。综合运用在课程学习过程中所学知识，同时为了实现课程设计的规定成果进行更深入的理论学习和实践拓展。培养独立思考和解决问题的能力，探索和创新的能力。具体如下：⑴复习、巩固Java语言的基础知识，进一步加

2、深对Java语言的理解和掌握；⑵课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力；⑶通过课程设计实践，训练并提高学生在查阅设计资料、运用标准与规范和应用计算机等方面的能力。1.2内容：求解最短路问题（Floyd算法）；功能要求：实现Floyd算法，求解最短路问题，用GUI界面实现。1.3主要任务：在java开发环境下，运用GUI用户界面技术，通过Floyd算法，实验对最短路问题的求解。要求通过对Floyd算法的学习，掌握其原理，运用Java语言来实现该算法流程，取得

3、最短路方案。通过GUI界面显示该最短路问题的网络图，并标记显示出最短路的路径。14交通运输学院课程设计第2章设计过程2.1设计思路2.1.1Floyd算法首先：对最短路问题中的Floyd算法有个较为深入的了解。其基本思想可简归纳如下：floyd算法是一个经典的动态规划算法。首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，floyd算法为这个目标重新做一个诠释。假设Ak(i,j)表示从i到j中途不经过索引比k大的点的最短路径。它将最短路径的概念做了限制，使得该限制有机会满足迭代关系，这个迭代关系就在于研究：假设Ak(i,j)已知，是否可以借此推导出Ak-1(

4、i,j)。经过分析，可得到最短路的关键式子： Ak(i,j)=min( Ak-1(i,j), Ak-1(i,k)+ Ak-1(k,j))，这是由Java实现Floyd算法的基本依据。简单说，依次扫描每一点(k)，并以该点作为中介点，计算出通过k点的其他任意两点(i,j)的最短距离，这就是floyd算法的精髓。具体做法：利用一个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使用图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长

5、度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K=0时,A(0)[i][j]=arcs[i][j]，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。简单概括为：  第一步，让所有边上加入中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的值，完成后得到A(1)，第二步，让所有边上加入中间顶点2，取A[i][j]与A[i][2]+A[2][j]中较小的值，完成后得到A(2)…，如此进行下去，当第

6、n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)[i][j]表示顶点i到顶点j的最短距离。2.1.2邻接矩阵在设计过程中，还会涉及一个重要概念：邻接矩阵。在图的邻接矩阵表示法中：　　①用邻接矩阵表示顶点间的相邻关系　　②用一个顺序表来存储顶点信息若G是网络，则邻接矩阵可定义为：14交通运输学院课程设计  　　其中：　　wij表示边上的权值;　　∞表示一个计算机允许的、大于所有边上权值的数。【例】下面带权图的两种邻接矩阵分别为A3和A4。  2.1.3图形用户界面为了达到最终目的，又对Java中的图形用户界面做了简单的学习，认识到Java不仅仅用于网络开发，也可以开

7、发应用程序。这就体现的GUI的作用所在。在学习了窗口的应用后，又对Graphics类，做了较多的学习。用于绘制图形和简单的图像处理，比如后面用到的画直线，画圆等.最后，经过多次调试，将Floyd算法与GUI界面结合起来，达到最终目的，即通过运用Java实现由图形用户界面显示Floyd算法。2.2设计内容及分析2.2.1算法部分声明部分：publicclassFloyd{int[][]length;//任意两点之间路径长度int[][][]path;//任意两点之间的路径publicFloyd(int[]