c++课设报告《基于Dijkstra算法的最短路径问题求解》[1].doc

课 程 设 计 任 务 书 学院信息科学与工程专业通信工程 学生姓名 * 学号 * 设计题目基于基于 DijkstraDijkstra 算法的最短路径问题求解算法的最短路径问题求解 内容及要求： 进行类的设计与实现，解决最短路径问题。具体要求如下： （1） 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储； （2） 采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径； （3） 将上述功能作为类的成员函数实现，编写主函数测试上述功能。 进度安排： 第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计； 第 18 周：程序的设计、调试与实现； 第 19 周：程序测试与分析，撰写课程设计报告，进行答辩验收。 指导教师（签字）： 年 月 日 学院院长（签字） 年 月 日 目目 录录 1 需求分析 .- 1 - 2 算法基本原理 .- 1 - 3 类设计 .- 2 - 4 详细设计 .- 3 - 4.1 类的接口设计 .- 3 - 4.2 类的实现 .- 5 - 4.3 主函数设计 .- 10 - 5 DOS 界面程序运行结果及分析 .- 11 - 5.1 程序运行结果 .- 11 - 5.2 运行结果分析- 12 - 6 基于 MFC 的图形界面程序开发.- 13 - 6.1 基于 MFC 的图形界面程序设计.- 13 - 6.2 程序测试- 15- 6.3 MFC 程序编写总结.- 17 - 7 参考文献 - 17- - 1 - 1 需求分析需求分析 Dijkstra 算法算法是由荷兰计算机科学家艾兹格迪科斯彻发现的。算法解决的是有 向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的 距离。 Dijkstra 算法可以用来找到两个城市之间的最短路径。 Dijkstra 算法的输入包含了一个有权重的有向图 G，以及 G 中的一个来源顶点 S。 我们以 V 表示 G 中所有顶点的集合。图中的每一个边，都是两个顶点所形 成的有序元素对。(u,v)表示从顶点 u 到 v 有路径相连。 假设 E为所有边的集 合，而边的权重则由权重函数 w: E 0, 定义。 因此，w(u,v)就是从顶点 u 到顶点 v 的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任 两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有 V 中有顶 点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花费路径(i.e. 最短路径)。 这个 算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。 1如果将交通网络化成带权图，假如用顶点表示城市，边表示公路段，则 由这些顶点和边组成的图可表示沟通个城市的公路图，边的权用以表示两个城 市之间的距离或者表示走过这段公路所需要的时间或通过这段路的难易程度等。 作为司机和乘汽车的人，自然会关心如下两个问题： （1）从甲地到乙地是否有公路？ （2）从甲地到乙地有几条公路，哪条公路最短或花费的代价最小？ 这就是我们要讨论的最短路径问题。 2.迪杰斯特拉提出的一个求最短路径的算法。其基本思想是：按路径长度 递增的顺序，逐个产生各最短路径。 3首先引进辅助向量 dist，它的每一个分量 disti表示已经找到的且 从源点到每一个终点的当前最短路径长度。它的初态为：如果从到有 0 v i v 0 v i v 弧，则 disti为弧的权值；否则 disti为。其中，长度为 distj =mindisti|V的路径是从出发的长度最短的一条最短路径，此路径为 i v 0 v （，） 。 0 v i v - 2 - 2 算法基本原理算法基本原理 根据以上分析，可以得到如下描述的算法： 假设用带权的邻接矩阵 arceij来表示带权有向图，arceij表示弧 上的权值。若不存在，则置 arceij为（在计算机上可 i v j v i v j v 用允许的最大值代替） 。S 为已找到的从出发的最短路径的终点的集合，它的 0 v 初始状态为空集。那么，从出发到图上其余个顶点（终点）可能达到的最 0 v i v 短路径长度的初值为： disti=arceLocate Vex(G,)iS 0 v i v 选择得 j v distj=mindisti|V-S i v 就是当前求得的一条从出发的最短路径的终点。令 S=Sj。 j v 0 v 修改从出发到集合 V-S 上任一顶点可达的最短顶点长度。如果 0 v k v distj+arcejka-n; int i,j; - 8 - for(i=0;in;i+) for(j=0;jn;j+) cina-pathij; if(a-pathij=-1) a-pathij=INF; a-src=0;/源点暂时定为 0，你自己改吧 a-Cal(); for(i=0;in;i+) cout“disi=“idisisrc=0;/源点暂时定为 0，然后通过循环语句，调用类中的函数，算出最短路径。 5 DOS 界面程序运行结果及分析界面程序运行结果及分析 5.1 程序运行结果 程序运行结果如图 2 所示。 - 9 - 图 2 程序运行结果 5.2 运行结果分析 整个程序中的矩阵存储采用的是一维数组和动态内存分配方式。 通过此类定义链接矩阵，采用图的邻接矩阵或邻接表实现最短路径问题中 图的存储，然后通过主函数 main 调用 class 来实现，采用 Dijkstra 算法求从 某个源点到其余各顶点的最短路径。 6 基于 MFC 的图形界面程序开发 MFC 的图形界面程序设计可在上述类设计的基础上进行改造，MFC 的图 形界面程序与 DOS 界面程序的主要不同点是：MFC 图形界面程序与 DOS 界面 - 10 - 程序的输入输出方式不同，DOS 界面程序采用字符交互式实现数据输入输出， 主要通过 cin，cout 等 I/O 流实现，而 MFC 的图形程序界面采用标准 Windows 窗口和控件实现输入输出，因此必须在 MFC 类的框架下加入上面所设计的矩阵 和方程组类，并通过图形界面的输入输出改造来完成。 6.1 基于 MFC 的图形界面程序设计 （1）界面设计）界面设计 首先在 VC 中建立 MFC AppWizard(exe)工程，名称为 GuassLineGUI，并在 向导的 Step1 中选择 Dialog based，即建立基于对话框的应用程序，如下图 45 所示。 图 4 建立 MFC AppWizard(exe)工程 图 5 建立基于对话框的应用程序 - 11 - 将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 6 所示。 （2）代码设置）代码设置 为了能够将对话框界面上的控件能够与代码联系起来，需要为 24 个 Edit Box 控件建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选 择 Member Variables 选项卡，可显示成员变量设置界面，如图 7 所示。 图 7 成员变量设置界面 通过该界面设置与 24 个 Edit Box 控件对应的成员变量，具体如表 2 所示。 表 2 控件基本信息 控件 ID成员变量类型成员变量名称 IDC_EDIT_A00 IDC_EDIT_A33doublem_1m_2 IDC_EDIT_b0 IDC_EDIT_b3doublem_2m_3 IDC_EDIT_X0 IDC_EDIT_X3doublem_3m_4 下面是编写代码的重要阶段，可以借鉴在设计基于 DOS 界面的控制台应用 程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。 将 class 文件，重新命名为 class.h，并将其加入 MFC 工程。 修改 class 文件具体包括： 将显示矩阵 PrintM()函数和显示方程 PrintL()函数注释掉，因为在图形 界面的程序上已经不需要连个函数承担输出功能了； 将输出方程组的解 ShowX()函数加入参数 double x变成 ShowX(double x)，以实现将所求的解输出至参数 x 中，并最终完成在对话框界面上 - 12 - 的显示； 将全选主元高斯法求解函数 Solve() 中的两处 cout 语句去掉，因为不需 要也不能够使用 cout 流实现输出。 在对话框类的实现文件 GuassLineGUIDlg.cpp 中加入#include “Linequ.h“，以实现在该文件中可使用 Linequ 类。 在 GuassLineGUIDlg.cpp 文件中加入以下全局变量的定义，以实现 GuassLineGUIDlg 类和 Linequ 类之间的通信，具体代码如下： double a=/系数矩阵 0.2368,0.2471,0.2568,1.2671, 0.1968,0.2071,1.2168,0.2271, 0.1581,1.1675,0.1768,0.1871, 1.1161,0.1254,0.1397,0.1490 ; double b4= 1.8471,1.7471,1.6471,1.5471; /方程右端项 double *X;/存放方程组的解 编写读入数据按钮的消息处理函数，实现将矩阵和右端项的数据刷新到 界面上，具体代码如下： void CGuassLineGUIDlg:OnBUTTONRead() / TODO: Add your control notification handler code here m_A00=a0; m_A01=a1; m_A02=a2; m_A03=a3; m_A10=a5; m_A11=a6; m_A12=a7; m_A13=a8; m_A20=a9; m_A21=a10; m_A22=a11; m_A23=a12; m_A30=a13; m_A31=a14; m_A32=a15; m_A33=a16; m_b0=b0; m_b1=b1; m_b2=b2; m_b3=b3; UpdateData(FALSE); 编写计算求解按钮的消息处理函数，实现将方程求解，具体代码如下： void CGuassLineGUIDlg:OnButtonCalc() / TODO: Add your control notification handler code here Linequ equ1(4); /定义一个四元方程组对象 - 13 - equ1.SetLinequ(a,b); /设置方程组 X=new double4; if(equ1.Solve() /求解方程组 equ1.ShowX(X);/输出方程组的解 m_X0=X0; m_X1=X1; m_X2=X2; m_X3=X3; UpdateData(FALSE); else MessageBox(“求解失败“);/求解失败 退出按钮比较简单，代码如下： void CGuassLineGUIDlg:OnBUTTONExit() / TODO: Add your control notification handler code here OnOK(); 6.2 程序测试 运行程序后，首先出现的界面如图 8 所示。 - 14 - 程序运行如下图： 图 8 程序初始运行界面 输入要求的邻接矩阵的最短路径，按最短路径按钮输出结果。 6.3 MFC 程序编写总结 MFC 程序与 DOS 界面程序编写的最大不同是程序员需要将编程精力放在 图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上，而 - 15 - 这些问题在 DOS 界面程序中是不存在的，因此，初学 MFC 的编程者会对此感 到困难，然而，当你编写出一个基于 Windows 界面的程序时，所获得的满足程 度远远大于简单的 DOS 界面程序，况且基于 Windows 的图形界面的程序设计 已成为主流，作为程序员而言，是非学会不可的。 本次课程设计作为编写 Windows 程序的初步尝试，能够实现程序的主要功 能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标， 本此编写的 MFC 程序虽然能实现所需功能，但从面向对象程序设计理念和图形 界面设计要求来说，尚存在不足，主要包括以下几个方面。 （1）使用全局变量存储邻接矩阵、输入加权值的数据 （2）将类的定义与实现放在