基于Floyd算法的最短路径问题的求解c1

《基于Floyd算法的最短路径问题的求解c1》由会员分享，可在线阅读，更多相关《基于Floyd算法的最短路径问题的求解c1（24页珍藏版）》请在装配图网上搜索。

1、摘 要现实生活中许多实际问题的解决依赖于最短途径的应用，其中比较常用的是floyd算法。通过floyd算法使最短途径问题变得简朴化。采用图的邻接矩阵或邻接表实现最短途径问题中图的存储。采用Visual C+6.0的控制台工程和MFC工程分别实现基于floyd算法求最短途径的应用。核心词：最短途径；floyd算法；邻接矩阵；MFC工程目 录1需求分析12算法基本原理12.1 邻接矩阵12.2 弗洛伊德算法23类设计23.1 类的概述23.2 类的接口设计33.3 类的实现44基于控制台的应用程序74.1 主函数设计74.2 运营成果及分析85基于MFC的应用程序95.1 图形界面设计95.1 程

2、序代码设计115.3 运营成果及分析20结 论21参照文献221 需求分析 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短途径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系专家罗伯特弗洛伊德命名。假若要在计算机上建立一种交通征询系统则可以采用图的构造来表达实际的交通网络。这个资讯系统可以回答游客提出的多种问题。例如，一位旅客要从A城到B城，她但愿选择一条途中中转次数至少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目至少的途径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终结。由此所得

3、广度优先生成树上，从根顶点A到顶点B的途径就是中转次数至少的途径，途径上A与B之间的顶点就是途径中的中转站数。但是这只是一类最简朴的图的最短途径的问题。有时对于旅客来说，也许更关怀的是节省交通费用；对于司机来说里程和速度则是她们感爱好的信息。为了在图上标示有关信息可对边赋以权的值，权的值表达两都市间的距离，或图中所需时间，或交通费用等等。此时途径长度的量度就不再是途径上边的数目，而是途径上边的权值之和。边赋以权值之后再结合最短途径算法来解决这些实际问题。Floyd算法是最短途径典型算法中形式较为简朴，便于理解的一种。2 算法基本原理2.1 邻接矩阵邻接矩阵（Adjacency Matrix）：

4、是表达顶点之间相邻关系的矩阵。设G=(V,E)是一种图，其中V=v1,v2,vn。G的邻接矩阵是一种具有下列性质的n阶方阵：（1）对无向图而言，邻接矩阵一定是对称的，并且对角线一定为零（在此仅讨论无向简朴图），有向图则不一定如此。（2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。（3）用邻接矩阵法表达图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，因此扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n/2个空间。2.2 弗洛伊德算法弗洛伊德算法使用图的邻接矩阵arcsn+1n+1来存储带权有向

5、图。算法的基本思想是：设立一种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中较小的值

6、，完毕后得到A(2)，如此进行下去，当第n步完毕后，得到A(n)，A(n)即为我们所求成果,A(n)ij表达顶点i到顶点j的最短距离。 因此弗洛伊德算法可以描述为:A(0)ij=arcsij; /arcs为图的邻接矩阵A(k)ij=minA(k-1) ij，A(k-1) ik+A(k-1) kj，其中 k=1,2,n（1）定义一种n阶方阵序列： D(-1)，D(0)，,D(n-1).D(-1) ij = G.arcsij；D(k) ij = min D(k-1)ij，D(k-1)ik + D(k-1)kj ，k = 0，1，n-1（2）其中D(0) ij是从顶点vi 到vj中间顶点是v0的最短

7、途径的长度；D(k) ij是从顶点vi 到vj中间顶点的序号不不小于k的最短途径长度；D(n-1)ij是从顶点vi 到vj 的最短途径长度。3 类设计3.1 类的概述类代表了某一批对象的共性和特性。类是对象的抽象。类这种数据类型中的数据既涉及数据也涉及操作数据的函数。声明类的一般形式：class 类名 private: 私有的数据和成员函数； public: 公用的数据和成员函数； ；定义对象：类名 对象名；可以在类外定义成员函数，在函数名前加上类名，“：”是作用域限定符或称作用域运算符用它阐明函数式属于哪个类的。如下面程序中的void MGraph:CreateMGraph(MGraph &

8、G) 函数体3.2 类的接口设计 #include#include #include using namespace std;#define MaxVertexNum 100#define INF 32767class MGraphprivate: char vertexMaxVertexNum; /顶点信息 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵 int n,e; /顶点数和边数 public: void CreateMGraph(MGraph &); /构造有向图 void Ppath(int100,int,int); void Dispath(i

9、nt100,int100,int); /输出最短途径 void Floyd(MGraph G); /Floyd算法的具体实现; 一方面将所需文献名写好，定义类MGraph。在进行类体构造时将数据char vertexMaxVertexNum、int edgesMaxVertexNumMaxVertexNum和int n,e定义为私有数据，将成员函数void CreateMGraph(MGraph &)、void Ppath(int100,int,int)、void Dispath(int100,int100,int)和void Floyd(MGraph G)定义为公用的，以便非类体内的数据调用

10、函数。3.3 类的实现void MGraph:CreateMGraph(MGraph &G)/构造有向图 int i,j,k,p; coutG.nG.e; cout请输入顶点元素:; for (i=0;iG.vertexi; for (i=0;iG.n;i+) for (j=0;jG.n;j+) G.edgesij=INF; if (i=j) G.edgesij=0; for (k=0;kG.e;k+) cout请输入第k+1ijp; G.edgesij=p; void MGraph:Ppath(int pathMaxVertexNum,int i,int j) /Ppath（）函数在path

11、中递归输出从顶点vi到vj的最短途径。 int k; k=pathij; if (k=-1) / pathij=i时,顶点vi和vj之间无中间顶点,也就是说找到了始节点 return; Ppath(path,i,k); printf(%d,k); Ppath(path,k,j); void MGraph:Dispath(int AMaxVertexNum,int pathMaxVertexNum,int n)/输出最短途径的算法 int i,j; for (i=0;in;i+) for (j=0;j途径长度:%d途径:,i,j,Aij); printf(%d,i); Ppath(path,i,

12、j); printf(%dn,j); void MGraph:Floyd(MGraph G) int AMaxVertexNumMaxVertexNum,pathMaxVertexNumMaxVertexNum; int i,j,k; for (i=0;iG.n;i+) for (j=0;jG.n;j+) Aij=G.edgesij; pathij=-1; for (k=0;kG.n;k+) / /向vi与vj之间中n次加入中间顶点 for (i=0;iG.n;i+) for (j=0;jAik+Akj) Aij=Aik+Akj; pathij=k;/ 表达从i节点到j节点,要通过k节点 Di

13、spath(A,path,G.n); 4 基于控制台的应用程序4.1 主函数设计int main() MGraph G; G.CreateMGraph(G); G.Floyd(G); return 0;在程序的主函数部分，定义一种MGrapha类的对象G，调用成员函数CreateMGraph()和Floyd()分别完毕了采用图的邻接矩阵实现最短途径问题中图的存储和采用Floyd算法求每一对顶点的最短途径的任务。4.2 运营成果及分析 将待测图的有关数据输入则得到如图1的运营成果。图1 程序运营成果从图1可以看出：整个程序中的矩阵存储采用的是一维数组和动态内存分派方式。通过此类定义邻接矩阵，采用

14、图的邻接矩阵实现最短途径问题中图的存储，然后通过主函数main调用class来实现，采用Floyd算法求每对顶点间最短途径从某个源点到其他各顶点的最短途径。将图的基本信息输入，顶点数和边数4、8，顶点元素A、B、C、D，8条弧各自的序号和权值。运营程序得出每对顶点间的最短途径长度和途径。基于Floyd算法成功的解决了最短途径问题。5 基于MFC的应用程序MFC的图形界面程序与DOS界面程序的重要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，重要通过cin，cout等I/O流实现，而MFC的图形程序界面采用原则Windows窗口和控

15、件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完毕。5.1 图形界面设计一方面在VC中建立MFC AppWizard（exe）工程，名称为最短途径，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如下图23所示。图2 建立MFC AppWizard（exe）工程图3 建立基于对话框的应用程序将对话框资源中的默认对话框运用工具箱改导致如下界面，如图4所示。图4体现式求值程序界面设计在图4的设计过程中，选择文献按钮用于进行文献的选择，选择文献后顶点个数也随之显示；起点和终点编辑框分别用于输入起点终点信息；提交

16、按钮用于输出最后成果。5.1 程序代码设计为了可以将对话框界面上的控件可以与代码联系起来，需要为5个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设立界面，如图5所示。图5 成员变量设立界面通过该界面设立与5个Edit Box控件相应的成员变量，具体如表1所示。 表1 控件基本信息控件ID成员变量类型成员变量名称IDC_EDIT_ENDintm_intEndIDC_EDIT_STARTintm_intStartIDC_EDIT_RESULTCstringm_intRes

17、ulIDC_EDIT_INFOCstringm_strFileinfoIDC_EDIT_NUMIntm_nNum在MFC中的重要代码：（1）.Ex_FloydDlg.cpp中的代码为：void CEx_exFloydDlg:OnButtonSel() /选择文献，并将文献中的数据保存到数组中/ TODO: Add your control notification handler code here CFileDialog file(TRUE, NULL, NULL, NULL, _T(*.txt)|*.txt|(*.doc)|*.doc|所有文献 (*.*)|*.*| |),NULL); /

18、*获得文献名*/CString strFileName;if(file.DoModal() = IDOK)m_strFileInfo = file.GetFileName();if(m_strFileInfo.IsEmpty()MessageBox(你还没有选择任何文献!);return;elseMessageBox(你选择文献:+ m_strFileInfo+请输入起点和终点);GetDlgItem(IDC_EDIT_START)-EnableWindow(true);GetDlgItem(IDC_EDIT_END)-EnableWindow(true);GetDlgItem(IDC_BUT

19、TON_SUBMIT)-EnableWindow(true);/将文献的数据读入到数组中 CStdioFile fp;if(!fp.Open(m_strFileInfo,CFile:modeRead)MessageBox(文献打开失败!);return;int i=0;CString str;char* temp;BOOL bread = fp.ReadString(str);temp = str.GetBuffer(0); n=atoi(temp); counts=n*n; int *tp; tp=new intcounts+1;m_nNUM=n;c=new int*n+1;for(i=1;

20、 i=n; i+)ci= new int n+1;a=new int*n+1;for(i=1; i=n; i+)ai= new int n+1;r=new int*n+1;for(i=1; i=n; i+)ri= new int n+1;bread = fp.ReadString(str);i=0;while(bread)temp = str.GetBuffer(0);tpi+ = atoi(temp);bread = fp.ReadString(str);fp.Close();/将一维数组转化为二维数组放到数组c中for(i = 0; icounts; i+)if(tpi != -1)ci/

21、n+1i%n+1 = tpi;elseci/n+1i%n+1 = maxint;UpdateData(FALSE);void CEx_exFloydDlg:Ex_floyd(int n,int *c,int *a,int *r)int i,j,k;for(i=1; i=n; i+)for(j=1; j=n; j+)aij=cij;rij=0;for(i=1; i=n; i+)for(j=1; j=n; j+)for(k=1; k=n; k+)if(aik+akj,k);m_strResult += strRes;Ex_output(r,k,j); return 0;void CEx_exFlo

22、ydDlg:OnButtonSubmit() /执行floyd算法计算最优值和最优解/ TODO: Add your control notification handler code hereUpdateData(TRUE); /接受编辑框的数据CString strData; Ex_floyd(n,c,a,r); if(m_intStartn|m_intStartn|m_intEnd,m_intStart);m_strResult += strRes;Ex_output(r,m_intStart,m_intEnd);strRes.Format(%d,m_intEnd);m_strResul

23、t += strRes;UpdateData(FALSE); /更新编辑框的数据（2）Ex_FloydDlg.h中的重要代码为：class CEx_exFloydDlg : public CDialog/ Constructionpublic:CEx_exFloydDlg(CWnd* pParent = NULL);/ standard constructorvoid Ex_floyd (int n,int *c,int *a,int *r);int Ex_output(int *r,int i,int j); / Dialog Data/AFX_DATA(CEx_exFloydDlg)enu

24、m IDD = IDD_EX_EXFLOYD_DIALOG ;CStringm_strFileInfo;intm_intEnd;intm_intStart;CStringm_strResult;intm_nNUM;protected:HICON m_hIcon;int n ; /图形中顶点的个数int *a; /最优值矩阵int *c;/顶点之间的距离矩阵int *r;/路由矩阵int counts;int *tp;CString strRes; / Generated message map functions/AFX_MSG(CEx_exFloydDlg)virtual BOOL OnIn

25、itDialog();afx_msg void OnSysCommand(UINT nID, LPARAM lParam);afx_msg void OnPaint();afx_msg HCURSOR OnQueryDragIcon();afx_msg void OnButtonSel();afx_msg void OnButtonSubmit();（3）两个外部调用函数模块：void CEx_exFloydDlg:Ex_floyd(int n,int *c,int *a,int *r)int i,j,k;for(i=1; i=n; i+)for(j=1; j=n; j+)aij=cij;ri

26、j=0;for(i=1; i=n; i+)for(j=1; j=n; j+)for(k=1; k=n; k+)if(aik+akj,k);m_strResult += strRes;Ex_output(r,k,j); return 0; if(file.DoModal() = IDOK)m_strFileInfo = file.GetFileName();if(m_strFileInfo.IsEmpty()MessageBox(你还没有选择任何文献!);return;elseMessageBox(你选择文献:+ m_strFileInfo+请输入起点和终点);GetDlgItem(IDC_ED

27、IT_START)-EnableWindow(true);GetDlgItem(IDC_EDIT_END)-EnableWindow(true);GetDlgItem(IDC_BUTTON_SUBMIT)-EnableWindow(true); /将文献的数据读入到数组中 CStdioFile fp;if(!fp.Open(m_strFileInfo,CFile:modeRead)MessageBox(文献打开失败!);return; int i=0;CString str;char* temp;BOOL bread = fp.ReadString(str);temp = str.GetBuf

28、fer(0); n=atoi(temp); counts=n*n; int *tp; tp=new intcounts+1;m_nNUM=n;c=new int*n+1;for(i=1; i=n; i+)ci= new int n+1;a=new int*n+1;for(i=1; i=n; i+)ai= new int n+1;r=new int*n+1;for(i=1; i=n; i+)ri= new int n+1;bread = fp.ReadString(str);i=0;while(bread)temp = str.GetBuffer(0);tpi+ = atoi(temp);bre

29、ad = fp.ReadString(str);fp.Close(); /将一维数组转化为二维数组放到数组c中for(i = 0; icounts; i+)if(tpi != -1)ci/n+1i%n+1 = tpi;elseci/n+1i%n+1 = maxint;UpdateData(FALSE);5.3 运营成果及分析先选择“选择文献按钮”，在其中选择一种文献后如1.txt。会在顶点个数只读编辑框中显示出你所选文献中的顶点个数，分别在起点和终点编辑框中输入起点和终点，在点击提交，会浮现如图5运营界面。图5单击提交按钮后的界面在图5中可以看出：进行操作时，单击选择文献框，选择所需要的文档，

30、该文档存储了待测图的所有信息，随后生成顶点个数。将你所要测的最短途径的一对顶点的起点和终点输入相应位置。待测信息输入完毕后，单击提交按钮，所测一对顶点的求出过程都会显示在成果相应的显示框中。成功的在MFC中实现了基于Floyd算法求每对顶点间的最短途径问题。MFC显示的界面，更清晰直观的反映出所规定解的最短途径问题，便于顾客的理解和操作。结 论本次课程设计重要研究基于Floyd算法的最短途径问题的求解。论文主体大体分为五个部分，第一部分简介了Floyd算法的需求分析；第二部分简介了算法的基本原理；第三部分重要是类设计，简介了类、类的接口设计和类的实现；第四部分是基于控制台的应用程序；第五部分是

31、基于MFC的应用程序。完整的论述了所研究的问题。编写程序过程中，一方面需要理解邻接矩阵的概念，才干采用图的邻接矩阵实现最短途径问题中图的储存，然后才干采用Floyd算法求每一对顶点的最短途径。实验过程中用两种方式来实现基于Floyd算法的最短途径问题求解：一种是Win32 Console Application，输入输出采用老式DOS的字符式交互界面；另一种是MFC AppWizard(exe)，输入输出采用基于Windows的图形式交互界面。编写DOS有关算法时采用类与对象进行编程，定义类MGraph，涉及的数据元素有顶点信息、邻接矩阵和顶点数和边数，还涉及成员函数void CreateMG

32、raph(MGraph &);用于构造有向图、void Ppath(int100,int,int);、void Dispath(int100,int100,int);实现输出最短途径、void Floyd(MGraph G);则是Floyd算法的具体实现。通过定义对象对成员函数进行调用，完毕基于floyd算法求最短途径问题。MFC虽然算法复杂，但是基于MFC的应用程序能更形象直接的供顾客使用。最后要感谢教师和同窗的协助，我才干成功的完毕这次课程设计的论文。这次课程设计作为学完面向对象程序设计课程后的一次全面的综合练习。通过这次设计增长我对面向对象程序设计的基本理论的理解，掌握面向对象程序设计开发的基本措施，进一步提高了综合运用所学知识的能力。参照文献1 谭浩强C+基本入门大全北京：清华大学出版社，:100-1022 郑莉，董渊，张瑞丰C+语言程序设计（第3版）北京：清华大学出版社，:25-603 钱能C+程序设计教程（第2版）北京：清华大学出版社，:100-1304 欧阳志宏，董霖，钟俊华MFC程序设计轻松入门北京：人民邮电出版社，5 严蔚敏，吴伟民数据构造（C语言版）北京：清华大学出版社，：168-192