1、目目 录录 第 1 章 引 言 2 1.1 目的： 2 1.2 内容：. 2 1.3 主要任务： 2 第 2 章 设计过程 3 2.1 设计思路 3 2.1.1Floyd 算法 3 2.1.2 邻接矩阵 . 3 2.1.3 图形用户界面 4 2.2 设计内容及分析. 4 2.2.1 算法部分. 4 2.2.2 图形界面处理部分： . 8 第 3 章 总 结 12 附 录 13 参考文献 17 交通运输学院课程设计 2 第第 1 章章 引引 言言 1.1 目的：目的： 发现课程学习中的不足和薄弱环节，予以补充和加强。综合运用在课程学习过程中 所学知识，同时为了实现课程设计的规定成果进行更深入的理
2、论学习和实践拓展。培养 独立思考和解决问题的能力，探索和创新的能力。具体如下： 复习、巩固Java语言的基础知识，进一步加深对Java语言的理解和掌握； 课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知 识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际， 实践编程的能力； 通过课程设计实践，训练并提高学生在查阅设计资料、运用标准与规范和应用计 算机等方面的能力。 1.2 内容：内容： 求解最短路问题（Floyd 算法） ； 功能要求：实现 Floyd 算法，求解最短路问题，用 GUI 界面实现。 1.3 主要任务：主要任务： 在java开发环境下
3、，运用GUI用户界面技术，通过Floyd算法，实验对最短路问题的 求解。要求通过对Floyd算法的学习，掌握其原理，运用Java语言来实现该算法流程， 取得最短路方案。通过GUI界面显示该最短路问题的网络图，并标记显示出最短路的路 径。 交通运输学院课程设计 3 第第 2 章章 设计过程设计过程 2.1 设计思设计思路路 2.1.1Floyd 算法算法 首先：对最短路问题中的 Floyd 算法有个较为深入的了解。其基本思想可简归纳如 下：floyd 算法是一个经典的动态规划算法。首先我们的目标是寻找从点 i 到点 j 的最 短路径。 从动态规划的角度看问题， floyd 算法为这个目标重新做一
4、个诠释。 假设 A k(i,j) 表示从 i 到 j 中途不经过索引比 k 大的点的最短路径。它将最短路径的概念做了限制， 使得该限制有机会满足迭代关系，这个迭代关系就在于研究：假设 A k(i,j)已知，是否 可以借此推导出 A k-1(i,j)。经过分析，可得到最短路的关键式子： Ak(i,j) = min( A k-1(i,j), Ak-1(i,k) + Ak-1(k,j) )，这是由 Java 实现 Floyd 算法的基本依据。 简单说，依次扫描每一点(k)，并以该点作为中介点，计算出通过 k 点的其他任意两点 (i,j)的最短距离，这就是 floyd 算法的精髓。 具体做法： 利用一
5、个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法 仍然使用图的邻接矩阵 arcsn+1n+1来存储带权有向图。算法的基本思想是:设置一个 n x n的矩阵 A(k)，其中除对角线的元素都等于 0 外，其它元素 a(k)ij表示顶点 i到顶 点 j 的路径长度，K 表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为 路径长度，没有有向边时，路径长度为，当 K=0 时, A (0)ij=arcsij，以后逐步尝 试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的 路径长度减少了，则以此新路径代替原路径，修改矩阵元素。简单概括为： 第一步， 让所有边上加入
6、中间顶点1， 取Aij与 Ai1+A1j中较小的值作 Aij 的值，完成后得到 A(1)， 第二步，让所有边上加入中间顶点 2，取 Aij与 Ai2+A2j中较小的值， 完成后得到 A (2)，如此进行下去，当第 n 步完成后，得到 A(n)，A(n)即为我们所求结 果,A (n)ij表示顶点 i 到顶点 j 的最短距离。 2.2.1 1.2.2 邻接矩阵邻接矩阵 在设计过程中，还会涉及一个重要概念：邻接矩阵。在图的邻接矩阵表示法中： 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息 若 G 是网络，则邻接矩阵可定义为： 交通运输学院课程设计 4 其中： w ij 表示边上的权值; 表示一个计算机允许的、大于所有边上权值的数。 【例】下面带权图的两种邻接矩阵分别为 A 3 和 A 4 。 2.2.1 1.3.3 图形用户界面图形用户界面 为了达到最终目的， 又对 Java 中的图形用户界面做了简单的学习， 认识到 Java 不 仅仅用于
