《基于Floyd算法的最短路径问题的求解计算机C++1》由会员分享，可在线阅读，更多相关《基于Floyd算法的最短路径问题的求解计算机C++1（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.
2、1 图形界面设计95.1 程序代码设计115.3 运行结果及分析20结 论21参考文献22II1 需求分析 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索
3、，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数。但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说，可能更关心的是节省交通费用；对于司机来说里程和速度则是他们感兴趣的信息。为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目，而是路径上边的权值之和。边赋以权值之后再结合最短路径算法来解决这些实际问题。Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。2 算法基本原理2.1 邻接矩阵邻接矩阵（Ad
4、jacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=v1,v2,vn。G的邻接矩阵是一个具有下列性质的n阶方阵：（1）对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图），有向图则不一定如此。（2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。（3）用邻接矩阵法表示图共需要n2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要nn-1/2个空间。2.2 弗洛伊德算法弗洛伊德算法使用图的
5、邻接矩阵arcsn+1n+1来存储带权有向图。算法的基本思想是：设置一个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)；第二步，让所有边上加入中间
6、顶点2，取Aij与Ai2+A2j中较小的值，完成后得到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) i
7、j是从顶点vi 到vj中间顶点是v0的最短路径的长度；D(k) ij是从顶点vi 到vj中间顶点的序号不大于k的最短路径长度；D(n-1)ij是从顶点vi 到vj 的最短路径长度。3 类设计3.1 类的概述类代表了某一批对象的共性和特征。类是对象的抽象。类这种数据类型中的数据既包含数据也包含操作数据的函数。声明类的一般形式：class 类名 private: 私有的数据和成员函数； public: 公用的数据和成员函数； ；定义对象：类名 对象名；可以在类外定义成员函数，在函数名前加上类名，“：”是作用域限定符或称作用域运算符用它说明函数式属于哪个类的。如下面程序中的void MGraph:C
8、reateMGraph(MGraph &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,
9、int); void Dispath(int100,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
11、 j) /Ppath（）函数在path中递归输出从顶点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,j); printf(%dn,j);
