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

1、课 程 设 计 任 务 书学院信息科学与工程专业通信工程学生姓名*学号*设计题目基于基于 DijkstraDijkstra 算法的最短路径问题求解算法的最短路径问题求解内容及要求：进行类的设计与实现，解决最短路径问题。具体要求如下：（1） 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；（2） 采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径；（3） 将上述功能作为类的成员函数实现，编写主函数测试上述功能。进度安排：第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计；第 18 周：程序的设计、调试与实现；第 19 周：程序测试与分析，撰写课程设计报告，进行答辩验收

2、。指导教师（签字）：年 月 日学院院长（签字）年 月 日目目 录录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

3、 需求分析需求分析Dijkstra 算法算法是由荷兰计算机科学家艾兹格迪科斯彻发现的。算法解决的是有向图中最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra 算法可以用来找到两个城市之间的最短路径。Dijkstra 算法的输入包含了一个有权重的有向图 G，以及 G 中的一个来源顶点S。 我们以 V 表示 G 中所有顶点的集合。图中的每一个边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点 u 到 v 有路径相连。 假设 E为所有边的集合，而边的权重则由权重函数 w: E 0, 定义。 因此，w(u,v)就是从顶点 u到顶点 v 的非

4、负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。1如果将交通网络化成带权图，假如用顶点表示城市，边表示公路段，则由这些顶点和边组成的图可表示沟通个城市的公路图，边的权用以表示两个城市之间的距离或者表示走过这段公路所需要的时间或通过这段路的难易程度等。作为司机和乘汽车的人，自然会关心如下两个问题：（1）从甲地到乙地是否有公路？（2）从甲地到

5、乙地有几条公路，哪条公路最短或花费的代价最小？这就是我们要讨论的最短路径问题。2.迪杰斯特拉提出的一个求最短路径的算法。其基本思想是：按路径长度递增的顺序，逐个产生各最短路径。 3首先引进辅助向量 dist，它的每一个分量 disti表示已经找到的且从源点到每一个终点的当前最短路径长度。它的初态为：如果从到有0viv0viv弧，则 disti为弧的权值；否则 disti为。其中，长度为 distj=mindisti|V的路径是从出发的长度最短的一条最短路径，此路径为iv0v（，） 。0viv- 2 -2 算法基本原理算法基本原理根据以上分析，可以得到如下描述的算法：假设用带权的邻接矩阵 arc

6、eij来表示带权有向图，arceij表示弧上的权值。若不存在，则置 arceij为（在计算机上可ivjvivjv用允许的最大值代替） 。S 为已找到的从出发的最短路径的终点的集合，它的0v初始状态为空集。那么，从出发到图上其余个顶点（终点）可能达到的最0viv短路径长度的初值为： disti=arceLocate Vex(G,)iS0viv选择得jv distj=mindisti|V-Siv就是当前求得的一条从出发的最短路径的终点。令 S=Sj。jv0v修改从出发到集合 V-S 上任一顶点可达的最短顶点长度。如果0vkv distj+arcejkdistk则修改 distk为 distk=di

7、stj+arcejk重复操作、共 n-1 次。由此求得从到图上其余各顶点的最短路径0v是依路径长度递增的序列。用 Dijkstra 算法求有向图 G 的顶点到其余顶点 v 的最短路径 Pv及其0v带权长度 Dv。 这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时，源点 s 的路径长度值被赋为 0（ds=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 外 dv= ）。当算法结束时，dv中储存的便是从 s 到v 的最短路径，或者是无穷大（如果路径不存在的话）。 - 3 - Dijs

8、tra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s到 v 的最短路径可以通过将边(u,v)添加到 s 到 u 的尾部来拓展。这条路径的长度是 du+w(u,v)。如果这个值比目前已知的 dv的值要小，我们可以用新值来替代当前 dv中的值。拓展边的操作一直执行到所有的 dv都代表从 s 到 v 最短路径的花费。这个算法经过适当的组织因而当 du达到它最终的值的时候，每条边(u,v)都只被拓展一次。算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 dv的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合 S 初始状态为空，而后每一步都有一个顶点

9、从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 du值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边(u,v)进行拓展。 Dijkstra(G，D，s) /用 Dijkstra 算法求有向网 G 的源点 s 到各顶点的最短路径长度 /以下是初始化操作 S=s；Ds=0； /设置初始的红点集及最短距离 for( all i V-S )do /对蓝点集中每个顶点 i Di=Gsi； /设置 i 初始的估计距离为 w /以下是扩充红点集 for(i=0;iDk+Gkj) /新红点 k 使原 Dj值变小时，用新路径的长度修改 Dj， /使 j 离 s 更近。 Dj=Dk

10、+Gkj； - 4 -3 类设计类设计 从上面的算法分析可以看到，根据算法设计了类 class SPFA，public: int n;表示图里面的点数，public: int pathMAXMAX;定义链接矩阵最多是1000 个点，public: int disMAX;定义源点到其他点的距离，public: int src;定义源点，bool usedMAX=false;定义点是否访问过了,初始化为未访问，初始化一下到各个点的距离，如果从 k 点走到 j 点的路很比原来的要短，那么更新，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，采用Dijkstra 算法求从某个源点到其余各顶点的最短

11、路径。第一步 先取意即到的距离为 0,而是对所赋的初 10W v1v1v jT v jT v值。第二步 利用已知,根据对进行修正。 1W v min,jiijT vW vw jT v第三步 对所有修正后的求出其最小者。其对应的点是所能 jT v kT vkv1v一步到达的点中最近的一个,由于所有。因此任何从其它点中转而jv 0W u jv到达的通路上的距离都大于直接到的距离,因此就是到kv1vkv kT v kT v1v的最短距离,所以在算法中令并从 s 中删去,若 k=n 则kv kkW vT vkv就是到的最短路线,计算结束。否则令回到第二步,继 knW vW v1vnvikvv续运算,直

12、到 k=n 为止。这样每一次迭代,得到到一点的最短距离,重复上述过程直到。1vkvknvvFloyd 算法的基本原理和实现方法为:如果一个矩阵其中表示 与ijDd0ijd i间的距离,若 与间无路可通,则为无穷大。 与间的最短距离存在经过jijijdij与间的和不经过两种情况,所以可以令,n(n 为节点数)。检查ijkk1,2,3,kn与的值,在此,与分别为目前所知的 到与到的最短距离,因ijdikkjddikdkjdikkj此,就是 到经过的最短距离。所以,若有,就表示从 出发ikkjddijkijikkjdddi经再到的距离要比原来的 到距离短,自然把 到的重写成。每kjijijijdik

13、kjdd- 5 -当一个搜索完,就是目前 到的最短距离。重复这一过程,最后当查完所有kijdij时,就为 到的最短距离。kijdij4 详细设计详细设计 首先，这个程序定义了一个类 class SPFA，通过此类定义链接矩阵，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，然后通过主函数 main调用 class 来实现，采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径。4.1 类的接口设计#includeusing namespace std;const int MAX=1000;const int INF=1000000000; class SPFApublic: int

14、 n;/表示图里面的点数public: int pathMAXMAX;/定义链接矩阵最多是 1000 个点public: int disMAX;/定义源点到其他点的距离public: int src;/定义源点经过公有派生，在类的接口定义了图里面的点数，定义链接矩阵最多是 1000 个点，定义源点到其他点的距离，定义源点经过公有派生，这些变量 int n，int pathMAXMAX，int disMAX，int src 都是 public 型。4.2 类的实现public:void Cal()- 6 -int i,j,k;bool usedMAX=false;/定义点是否访问过了,初始化为未

15、访问for(i=0;in;i+)/初始化一下到各个点的距离disi=pathsrci;dissrc=0;int min_=INF;for(i=0;in;i+)k=-1;min_=INF;for(j=0;jn;j+)if(disjmin_&!usedj)min_=disj;k=j;if(k=-1)/已经找不到有路可走的点return;usedk=true;for(j=0;jmin_+pathkj)/如果从 k 点走到 j 点的路很比原来的要短，那么更新disj=min_+pathkj;- 7 -;在类的成员函数实现过程中，设计了几个循环语句，和判断语句，定义点是否访问过了,初始化为未访问

16、，初始化一下到各个点的距离，已经找不到有路可走的点，if(!usedj&disjmin_+pathkj)/如果从 k 点走到 j 点的路很比原来的要短，那么更新4.3 主函数设计int main()/按照下面的数据格式输入,-1 表示没有路,自己到自己是 0/*30 -1 -13 0 -13 4 030 100 13 0 -13 4 030 1 23 0 -13 4 0*/SPFA* a=new SPFA();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;

17、a-src=0;/源点暂时定为 0，你自己改吧a-Cal();for(i=0;in;i+)coutdisi=idisisrc=0;/源点暂时定为 0，然后通过循环语句，调用类中的函数，算出最短路径。5 DOS 界面程序运行结果及分析界面程序运行结果及分析5.1 程序运行结果程序运行结果如图 2 所示。- 9 -图 2 程序运行结果5.2 运行结果分析整个程序中的矩阵存储采用的是一维数组和动态内存分配方式。通过此类定义链接矩阵，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，然后通过主函数 main 调用 class 来实现，采用 Dijkstra 算法求从某个源点到其余各顶点的最短路径。6

18、 基于 MFC 的图形界面程序开发MFC 的图形界面程序设计可在上述类设计的基础上进行改造，MFC 的图形界面程序与 DOS 界面程序的主要不同点是：MFC 图形界面程序与 DOS 界面- 10 -程序的输入输出方式不同，DOS 界面程序采用字符交互式实现数据输入输出，主要通过 cin，cout 等 I/O 流实现，而 MFC 的图形程序界面采用标准 Windows窗口和控件实现输入输出，因此必须在 MFC 类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。6.1 基于 MFC 的图形界面程序设计（1）界面设计）界面设计首先在 VC 中建立 MFC AppWizar

19、d(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 选项卡，可显示成员变量

20、设置界面，如图 7 所示。图 7 成员变量设置界面通过该界面设置与 24 个 Edit Box 控件对应的成员变量，具体如表 2 所示。表 2 控件基本信息控件 ID成员变量类型成员变量名称IDC_EDIT_A00 IDC_EDIT_A33doublem_1m_2IDC_EDIT_b0 IDC_EDIT_b3doublem_2m_3IDC_EDIT_X0 IDC_EDIT_X3doublem_3m_4下面是编写代码的重要阶段，可以借鉴在设计基于 DOS 界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。将 class 文件，重新命名为 class.h，并将其加入 MFC

21、 工程。修改 class 文件具体包括：将显示矩阵 PrintM()函数和显示方程 PrintL()函数注释掉，因为在图形界面的程序上已经不需要连个函数承担输出功能了；将输出方程组的解 ShowX()函数加入参数 double x变成 ShowX(double x)，以实现将所求的解输出至参数 x 中，并最终完成在对话框界面上- 12 -的显示；将全选主元高斯法求解函数 Solve() 中的两处 cout 语句去掉，因为不需要也不能够使用 cout 流实现输出。在对话框类的实现文件 GuassLineGUIDlg.cpp 中加入#include Linequ.h，以实现在该文件中可使用 Lin

22、equ 类。在 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;/存放方程组的解编写读入数据按钮的消息处理函数，实现将矩阵和右端

23、项的数据刷新到界面上，具体代码如下：void CGuassLineGUIDlg:OnBUTTONRead() / TODO: Add your control notification handler code herem_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;

24、m_b3=b3;UpdateData(FALSE);编写计算求解按钮的消息处理函数，实现将方程求解，具体代码如下：void CGuassLineGUIDlg:OnButtonCalc() / TODO: Add your control notification handler code hereLinequ 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);elseMessageBox(求解失败);/求解失败退出按钮比较简单，代码如下：void CGuassLineGUIDlg:OnBUTTONExit(