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

课 程 设 计 任 务 书学院信息科学与工程专业通信工程学生***学号*********设计题目基于Dijkstra算法的最短路径问题求解容及要求：进行类的设计与实现，解决最短路径问题具体要求如下：（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 需求分析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[]，它的每一个分量dist[i]表示已经找到的且从源点到每一个终点的当前最短路径长度它的初态为：如果从到有弧，那么dist[i]为弧的权值；否那么dist[i]为∞其中，长度为dist[j]=min{dist[i]|∈V}的路径是从出发的长度最短的一条最短路径，此路径为〔，〕2 算法基本原理根据以上分析，可以得到如下描述的算法：①假设用带权的邻接矩阵arce[i][j]来表示带权有向图，arce[i][j]表示弧<，>上的权值假设<,>不存在，那么置arce[i][j]为∞〔在计算机上可用允许的最大值代替〕S为已找到的从出发的最短路径的终点的集合，它的初始状态为空集那么，从出发到图上其余个顶点〔终点〕可能达到的最短路径长度的初值为： dist[i]=arce[Locate Vex(G,)][i]∈S②选择得 dist[j]=min{dist[i]|∈V-S}就是当前求得的一条从出发的最短路径的终点令S=S∪{j}③修改从出发到集合V-S上任一顶点可达的最短顶点长度。

如果 dist[j]+arce[j][k]

这个算法经过适当的组织因而当d[u]达到它最终的值的时候，每条边(u,v)都只被拓展一次算法维护两个顶点集S和Q集合S保留了我们的所有d[v]的值已经是最短路径的值顶点，而集合Q那么保留其他所有顶点集合S初始状态为空，而后每一步都有一个顶点从Q移动到S这个被选择的顶点是Q中拥有最小的d[u]值的顶点当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展 Dijkstra(G，D，s){    //用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度    //以下是初始化操作      S={s}；D[s]=0； //设置初始的红点集及最短距离      for( all i∈ V-S )do //对蓝点集中每个顶点i          D[i]=G[s][i]； //设置i初始的估计距离为w       //以下是扩充红点集      for(i=0;i

           S=S∪{k}； //将蓝点k涂红后扩充到红点集           for( all j∈V-S )do //调整剩余蓝点的估计距离               if(D[j]>D[k]+G[k][j])                //新红点k使原D[j]值变小时，用新路径的长度修改D[j]，              //使j离s更近                   D[j]=D[k]+G[k][j]；          }   }3 类设计从上面的算法分析可以看到，根据算法设计了类class SPFA，public: int n;表示图里面的点数，public: int path[MAX][MAX];定义矩阵最多是1000个点，public: int dis[MAX];定义源点到其他点的距离，public: int src;定义源点，bool used[MAX]={false};定义点是否访问过了,初始化为未访问，初始化一下到各个点的距离，如果从k点走到j点的路很比原来的要短，那么更新，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，采用Dijkstra算法求从某个源点到其余各顶点的最短路径。

第一步 先取意即到的距离为0,而是对所赋的初值第二步 利用,根据对进行修正第三步 对所有修正后的求出其最小者其对应的点是所能一步到达的点中最近的一个,由于所有因此任何从其它点中转而到达的通路上的距离都大于直接到的距离,因此就是到的最短距离,所以在算法中令并从s中删去,假设k=n那么就是到的最短路线,计算结束否那么令回到第二步,继续运算,直到k=n为止这样每一次迭代,得到到一点的最短距离,重复上述过程直到Floyd算法的基本原理和实现方法为:如果一个矩阵其中表示与间的距离,假设与间无路可通,那么为无穷大与间的最短距离存在经过与间的和不经过两种情况,所以可以令,n(n为节点数)检查与的值,在此,与分别为目前所知的到与到的最短距离,因此,就是到经过的最短距离所以,假设有,就表示从出发经再到的距离要比原来的到距离短,自然把到的重写成每当一个搜索完,就是目前到的最短距离重复这一过程,最后当查完所有时,就为到的最短距离4 详细设计首先，这个程序定义了一个类class SPFA，通过此类定义矩阵，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，然后通过主函数main调用class来实现，采用Dijkstra算法求从某个源点到其余各顶点的最短路径。

4.1 类的接口设计#includeusing namespace std;const int MAX=1000;const int INF=1000000000; class SPFA{public: int n;//表示图里面的点数public: int path[MAX][MAX];//定义矩阵最多是1000个点public: int dis[MAX];//定义源点到其他点的距离public: int src;//定义源点经过公有派生，在类的接口定义了图里面的点数，定义矩阵最多是1000个点，定义源点到其他点的距离，定义源点经过公有派生，这些变量int n，int path[MAX][MAX]，int dis[MAX]，int src都是public型4.2 类的实现public:void Cal() { int i,j,k; bool used[MAX]={false};//定义点是否访问过了,初始化为未访问 for(i=0;imin_+path[k][j])//如果从k点走到j点的路很比原来的要短，那么更新 { dis[j]=min_+path[k][j]; } } } }};在类的成员函数实现过程中，设计了几个循环语句，和判断语句，定义点是否访问过了,初始化为未访问，初始化一下到各个点的距离，已经找不到有路可走的点，if(!used[j]&&dis[j]>min_+path[k][j])//如果从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(); cout<<"请输入点数:"; cin>>a->n; int i,j; for(i=0;in;i++) { for(j=0;jn;j++) { cin>>a->path[i][j]; if(a->path[i][j]==-1) { a->path[i][j]=INF; } } } a->src=0;//源点暂时定为0，你自己改吧 a->Cal(); for(i=0;in;i++) { cout<<"dis[i]="<dis[i]<src=0;//源点暂时定为0，然后通过循环语句，调用类中的函数，算出最短路径。

5 DOS界面程序运行结果及分析5.1 程序运行结果程序运行结果如图2所示图2 程序运行结果5.2运行结果分析整个程序中的矩阵存储采用的是一维数组和动态存分配方式通过此类定义矩阵，采用图的邻接矩阵或邻接表实现最短路径问题中图的存储，然后通过主函数main调用class来实现，采用Dijkstra算法求从某个源点到其余各顶点的最短路径6 基于MFC的图形界面程序开发MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成6.1 基于MFC的图形界面程序设计〔1〕界面设计首先在VC中建立MFC AppWizard(exe)工程，名称为GuassLineGUI，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如下列图4~5所示。

图4 建立MFC AppWizard(exe)工程图5 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图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_1~m_2IDC_EDIT_b0~ IDC_EDIT_b3doublem_2~m_3IDC_EDIT_X0~ IDC_EDIT_X3doublem_3~m_4下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与容如下①将class文件，重新命名为class.h，并将其加入MFC工程②修改class文件具体包括：l 将显示矩阵PrintM()函数和显示方程PrintL()函数注释掉，因为在图形界面的程序上已经不需要连个函数承担输出功能了；l 将输出方程组的解ShowX() 函数加入参数double x[]变成ShowX(double x[])，以实现将所求的解输出至参数x中，并最终完成在对话框界面上的显示；l 将全选主元高斯法求解函数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 b[4]={ 1.8471,1.7471,1.6471,1.5471}; //方程右端项double *X; //存放方程组的解⑤编写读入数据按钮的消息处理函数，实现将矩阵和右端项的数据刷新到界面上，具体代码如下：void CGuassLineGUIDlg::OnBUTTONRead() { // TODO: Add your control notification handler code here m_A00=a[0]; m_A01=a[1]; m_A02=a[2]; m_A03=a[3]; m_A10=a[5]; m_A11=a[6]; m_A12=a[7]; m_A13=a[8]; m_A20=a[9]; m_A21=a[10]; m_A22=a[11]; m_A23=a[12]; m_A30=a[13]; m_A31=a[14]; m_A32=a[15]; m_A33=a[16]; m_b0=b[0]; m_b1=b[1]; m_b2=b[2]; m_b3=b[3]; UpdateData(FALSE);}⑥编写计算求解按钮的消息处理函数，实现将方程求解，具体代码如下：void CGuassLineGUIDlg::OnButtonCalc() { // TODO: Add your control notification handler code here Linequ equ1(4); //定义一个四元方程组对象 equ1.SetLinequ(a,b); //设置方程组 X=new double[4]; if(equ1.Solve()) //求解方程组 { equ1.ShowX(X); //输出方程组的解 m_X0=X[0]; m_X1=X[1]; m_X2=X[2]; m_X3=X[3]; UpdateData(FALSE); } else MessageBox("求解失败"); //求解失败}⑦退出按钮比较简单，代码如下：void CGuassLineGUIDlg::OnBUTTONExit() { // TODO: Add your control notification handler code here OnOK();}6.2 程序测试运行程序后，首先出现的界面如图8所示。

程序运行如下列图：图8 程序初始运行界面输入要求的邻接矩阵的最短路径，按最短路径按钮输出结果6.3 MFC程序编写总结MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上，而这些问题在DOS界面程序中是不存在的，因此，初学MFC的编程者会对此感到困难，然而，当你编写出一个基于Windows界面的程序时，所获得的满足程度远远大于简单的DOS界面程序，况且基于Windows的图形界面的程序设计已成为主流，作为程序员而言，是非学会不可的本次课程设计作为编写Windows程序的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，本此编写的MFC程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，主要包括以下几个方面〔1〕使用全局变量存储邻接矩阵、输入加权值的数据〔2〕将类的定义与实现放在同一个头文件class中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件〔3〕输入邻接矩阵，显示最短路径7 参考文献[1]X士良. C常用算法程序集. :清华大学,1995[2]莉,董渊,瑞丰. C++语言程序设计(第3版). :清华大学,2007[3]钱能. C++程序设计教程(第二版). :清华大学,2007[4]志泊,王春玲. 面向对象的程序设计语言—C++. :人民邮电,2002[5]庆扬,王能超,易大义. 数值分析. :华中理工大学,1986-。