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+arcejk /以下是扩充红点集 for(i=0;iDk+Gkj) /新红点 k 使原 Dj值变小时，用新路径的长度修改 Dj， /使 j 离 s 更近。 Dj=Dk+Gkj； - 4 - 3 类设计类设计 从上面的算法分析可以看到，根据算法设计了类 class SPFA，public: int n;表示图里面的点数，public: int pathMAXMAX;定义链接矩阵最多是 1000 个点，public: int disMAX;定义源点到其他点的距离，public: int src;定 义源点，bool usedMAX=false;定义点是否访问过了,初始化为未访问，初 始化一下到各个点的距离，如果从 k 点走到 j 点的路很比原来的要短，那么 更新，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径。 第一步 先取意即到的距离为 0,而是对所赋的初 1 0W v 1 v 1 v j T v j T v 值。 第二步 利用已知,根据对进行修正。 1 W v min, jiij T vW vw j T v 第三步 对所有修正后的求出其最小者。其对应的点是所能 j T v k T v k v 1 v 一步到达的点中最近的一个,由于所有。因此任何从其它点中转而 j v 0W u j v 到达的通路上的距离都大于直接到的距离,因此就是到 k v 1 v k v k T v k T v 1 v 的最短距离,所以在算法中令并从 s 中删去,若 k=n 则 k v kk W vT v k v 就是到的最短路线,计算结束。否则令回到第二步,继 kn W vW v 1 v n v ik vv 续运算,直到 k=n 为止。 这样每一次迭代,得到到一点的最短距离,重复上述过程直到。 1 v k v kn vv Floyd 算法的基本原理和实现方法为:如果一个矩阵其中表示 与 ij Dd 0 ij d i 间的距离,若 与间无路可通,则为无穷大。 与间的最短距离存在经过jij ij dij 与间的和不经过两种情况,所以可以令,n(n 为节点数)。检查ijkk1,2,3,kn 与的值,在此,与分别为目前所知的 到与到的最短距离,因 ij d ikkj dd ik d kj dikkj 此,就是 到经过的最短距离。所以,若有,就表示从 出发 ikkj ddijk ijikkj dddi 经再到的距离要比原来的 到距离短,自然把 到的重写成。每kjijij ij d ikkj dd - 5 - 当一个搜索完,就是目前 到的最短距离。重复这一过程,最后当查完所有k ij dij 时,就为 到的最短距离。k ij dij 4 详细设计详细设计 首先，这个程序定义了一个类 class SPFA，通过此类定义链接矩阵，采 用图的邻接矩阵或邻接表实现最短路径问题中图的存储，然后通过主函数 main 调用 class 来实现，采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径。 4.1 类的接口设计 #include using namespace std; const int MAX=1000; const int INF=1000000000; class SPFA public: int n;/表示图里面的点数 public: int pathMAXMAX;/定义链接矩阵最多是 1000 个点 public: int disMAX;/定义源点到其他点的距离 public: int src;/定义源点经过公有派生， 在类的接口定义了图里面的点数，定义链接矩阵最多是 1000 个点，定义源 点到其他点的距离，定义源点经过公有派生，这些变量 int n，int pathMAX MAX，int disMAX，int src 都是 public 型。 4.2 类的实现 public:void Cal() - 6 - int i,j,k; bool usedMAX=false;/定义点是否访问过了,初始化为未访问 for(i=0;imin_+pathkj)/如果从 k 点走到 j 点的 路很比原来的要短，那么更新 disj=min_+pathkj; - 7 - ; 在类的成员函数实现过程中，设计了几个循环语句，和判断语句，定义点 是否访问过了,初始化为未访问，初始化一下到各个点的距离，已经找不到有路 可走的点，if(!usedj couta-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+) coutdisisrc=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 - 程序运行如下图：