交通运输学院课程设计.doc

交通运输学院课程设计目 录第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参考文献17第1章 引 言1.1目的：发现课程学习中的不足和薄弱环节，予以补充和加强。综合运用在课程学习过程中所学知识，同时为了实现课程设计的规定成果进行更深入的理论学习和实践拓展。培养独立思考和解决问题的能力，探索和创新的能力。具体如下：复习、巩固Java语言的基础知识，进一步加深对Java语言的理解和掌握；课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力；通过课程设计实践，训练并提高学生在查阅设计资料、运用标准与规范和应用计算机等方面的能力。1.2 内容：求解最短路问题（Floyd算法）；功能要求：实现Floyd算法，求解最短路问题，用GUI界面实现。1.3主要任务：在java开发环境下，运用GUI用户界面技术，通过Floyd算法，实验对最短路问题的求解。要求通过对Floyd算法的学习，掌握其原理，运用Java语言来实现该算法流程，取得最短路方案。通过GUI界面显示该最短路问题的网络图，并标记显示出最短路的路径。第2章 设计过程2.1设计思路2.1.1Floyd算法首先：对最短路问题中的Floyd算法有个较为深入的了解。其基本思想可简归纳如下：floyd算法是一个经典的动态规划算法。首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，floyd算法为这个目标重新做一个诠释。假设Ak(i,j)表示从i到j中途不经过索引比k大的点的最短路径。它将最短路径的概念做了限制，使得该限制有机会满足迭代关系，这个迭代关系就在于研究：假设Ak(i,j)已知，是否可以借此推导出Ak-1(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算法的精髓。具体做法：利用一个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使用图的邻接矩阵arcsn+1n+1来存储带权有向图。算法的基本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=0时, A (0)ij=arcsij，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。简单概括为： 第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成后得到A(1)，第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)ij表示顶点i到顶点j的最短距离。2.1.2邻接矩阵在设计过程中，还会涉及一个重要概念：邻接矩阵。在图的邻接矩阵表示法中： 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息若G是网络，则邻接矩阵可定义为： 其中： w ij 表示边上的权值; 表示一个计算机允许的、大于所有边上权值的数。【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。 2.1.3图形用户界面为了达到最终目的，又对Java中的图形用户界面做了简单的学习，认识到Java 不仅仅用于网络开发，也可以开发应用程序。这就体现的GUI的作用所在。在学习了窗口的应用后，又对Graphics类，做了较多的学习。用于绘制图形和简单的图像处理，比如后面用到的画直线，画圆等.最后，经过多次调试，将Floyd算法与GUI界面结合起来，达到最终目的，即通过运用Java实现由图形用户界面显示Floyd算法。2.2设计内容及分析2.2.1 算法部分声明部分：public class Floyd int length ;/ 任意两点之间路径长度 int path ;/ 任意两点之间的路径public Floyd(int G) int MAX = 100; int row = G.length;/ 图G的行数 int spot = new introwrow;/ 定义任意两点之间经过的点 int onePath = new introw;/ 记录一条路径 length = new introwrow; path = new introwrow; 对路径的处理部分：for (int i = 0; i row; i+) / 处理图两点之间的路径 for (int j = 0; j row; j+) if (Gij = 0) Gij = MAX;/ 没有路径的两个点之间的路径为默认最大 if (i = j) Gij = 0;/ 本身的路径长度为0 for (int i = 0; i row; i+) / 初始化为任意两点之间没有路径 for (int j = 0; j row; j+) spotij = -1; for (int i = 0; i row; i+) / 假设任意两点之间的没有路径 onePathi = -1; 找最短路的过程部分：for (int v = 0; v row; +v) for (int w = 0; w row; +w) lengthvw = Gvw; for (int u = 0; u row; +u) for (int v = 0; v row; +v) for (int w = 0; w row; +w) if (lengthvw lengthvu + lengthuw) lengthvw = lengthvu + lengthuw;/ 如果存在更短路径则取更短路径 spotvw = u;/ 把经过的点加入 for (int i = 0; i row; i+) / 求出所有的路径 int point = new int1; for (int j = 0; j row; j+) point0 = 0; onePathpoint0+ = i; outputPath(spot, i, j, onePath, point); pathij = new intpoint0; for (int s = 0; s point0; s+) pathijs = onePaths; 记录最短路部分：void outputPath(int spot, int i, int j, int onePath, int point) / 输出i到j 的路径的实际代码,point记录一条路径的长度 if (i = j) return; if (spotij = -1) onePathpoint0+ = j; else outputPath(spot, i, spotij, onePath, point); outputPath(spot, spotij, j, onePath, point); 主函数部分： public static void main(String args) System.out.println(请输入所求问题的中间节点数：); int row; Scanner shuru=new Scanner(System.in); row=shuru.nextInt(); System.out.println(请依次输入两节点间的距离：); int n,m; int data=new introwrow; for(m=0;mrow;m+) for(n=0;nrow;n+) datamn=shuru.nextInt(); System.out.println(原矩阵为：);for(int i=0;irow;i+)for(int j=0;jrow;j+)System.out.printf(%4d,dataij);System.out.println();对输入数据进行处理：for (int i = 0; i data.length; i+) for (int j = i; j data.length; j+)if (dataij != dataji) return; Floyd test=new Floyd(data); for (int i = 0; i data.length; i+) for (int j = i; j datai.length; j+) System.out.println(); System.out.print(从v+i+到v+j+所经过的点有: ); /输出经过的路点for (int k = 0; k test.pathij.length; k+) System.out.print(test.pathijk + ); System.out.println(); System.out.println(从v+i+到v+j+最短路径长度是: + test.lengthij);/ 输出最短路部分 部分截图如图1，图2： 图1图22.2.2图形界面处理部分：外层窗体 ：public static void main(String args) ComputerFrame fr=new ComputerFrame(); fr.setTitle(Floyd算法求最短路问题); class ComputerFrame extends JFrame implements TextListener TextArea text1,text2; public ComputerFrame() setLayout(new FlowLayout(); text1=new TextArea(10,30);/确定文本区的大小 text2=new TextArea(10,30); add(text1); add(text2); text2.setEditable(false); text1.addTextListener(this); setSize(300,400); setVisible(true); addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent e) System.exit(0); ); validate(); 生成如图3的一个两个文本框的窗体。上面用来输入数据，下面用来显示路径图； 图3内部画图部分：public void actionPerformed(ActionEvent e) int a=Integer.parseInt(text1.getText(); int b=Integer.parseInt(text2.getText(); text3.setText(String.valueOf(shuzua-1b-1); public void paint(Graphics g) super.paint(g); Graphics2D g1 = (Graphics2D)g; /Ellipse2D.Double /public Ellipse2D.Double(double x,double y,double w,double h) / 根据指定坐标构造和初始化 Ellipse2D 参数： Ellipse2D e1 = new Ellipse2D.Double(40,60 ,20,20); Ellipse2D e2 = new Ellipse2D.Double(200,60,20,20); Ellipse2D e3 = new Ellipse2D.Double(200,200,20,20); Ellipse2D e4 = new Ellipse2D.Double(40,200,20,20); Ellipse2D e5 = new Ellipse2D.Double(320,130,20,20); Ellipse2D e6 = new Ellipse2D.Double(400,220,20,20); /x - 窗体矩形左上角的 X 坐标,y - 窗体矩形左上角的 Y 坐标,w - 窗体矩形的宽度,h - 窗体矩形的高度 g1.setPaint(Color.RED); g1.draw(e1); g1.drawString(V1, 45, 75); g1.draw(e2); g1.drawString(V2, 205,75); g1.draw(e3); g1.drawString(V3, 45, 215); g1.draw(e4); g1.drawString(V4, 205, 215); g1.draw(e5); g1.drawString(V5, 325, 145); g1.draw(e6); g1.drawString(V6, 400, 180); g1.drawLine(60, 70, 200,70); g1.drawString(3, 130, 70); g1.drawLine(50, 80, 50, 200); g1.drawString(5, 40, 135); g1.drawLine(60, 210,200 ,210); g1.drawString(2, 130,210); g1.drawLine(210, 80, 210,200); g1.drawString(4, 200, 135); g1.drawLine(55, 75, 203, 203); g1.drawString(8, 110, 120); g1.drawLine(55, 203, 203, 75); g1.drawString(6, 85, 170); g1.drawLine(220, 70, 320, 140); g1.drawString(11, 280,110); g1.drawLine(220, 210,320, 140); g1.drawString(10, 280, 160); 第3章 总 结通过本次课程设计，基本上解决了Floyd算法求解最短路径问题，这使我更加深入的了解了Java语言对于实际应用的意义。更主要的是，我深深的意识到，我对图形用户界面有关方面知识的严重匮乏，对它的学习有十分的必要性。尤其是在这次课程设计中，并没有对图形用户界面有很好的应用，没能对Floyd算法完全由GUI来实现，没能完全符合老师的要求，还希望老师能够见谅。这一点也正是我尚待解决的重要问题。附 录 2package floyd;public class Floyd_0 int length = null;int path = null; public Floyd_0 (int G) int MAX = 100; int row = G.length; int spot = new introwrow;int onePath = new introw; length = new introwrow; path = new introwrow; for (int i = 0; i row; i+) for (int j = 0; j row; j+) if (Gij = 0) Gij = MAX;if (i = j) Gij = 0; for (int i = 0; i row; i+) for (int j = 0; j row; j+)spotij = -1; for (int i = 0; i row; i+) onePathi = -1; for (int v = 0; v row; +v) for (int w = 0; w row; +w) lengthvw = Gvw; for (int u = 0; u row; +u) for (int v = 0; v row; +v) for (int w = 0; w row; +w) if (lengthvw lengthvu + lengthuw) lengthvw = length