数据结构_图的最短路径实现.docx

数据结构实验 课程名称 数据结构实验 题目名称 图的最短路径实现 学生学院 应用数学学院 专业班级 信息计算1 班 学 号 3114008104 学生姓名 陈辉腾 指导教师 刘志煌 2016年6月13日图的最短路径实现14信计1班陈辉腾3114008104实验要求：广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。 实验目的：进一步了解数据结构中对图的各种操作，以及求最短路径的算法。实验内容：编程求解上述题目（实验要求）思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v的最短路径保存到Dv，以及途经的一个最近新的路径保存Pathv。最后输出Dv以及Pathv。构造领接矩阵代码如下（详细思路写在代码注释里面）：其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）数据类型定义：构造上述领接矩阵函数代码：运行结果如下：求最短距离和路径函数如下：其中，PassPath(Path,i,v0)函数实现如下：SetName(i)函数（根据矩阵的行列数i，获得对应的城市名）实现如下：运行求解结果为：总结：一开始觉得图的好难，不过，确实很难啊，图比树复杂多了。其实还有一部分原因是自己对图比较陌生的缘故吧。对于这个求最短路径的算法的难点，个人觉得是在输出路径那里，巧妙的用到了递归。还有我觉得，怎么把巧妙的吧途经最短路径保存下来？处理这个问题我就觉得是一个难点，把这个问题处理的好，输出时就比较不用那么麻烦。书本是用一个二维数组p和一个一维数组p来处理，两个数组名还一样，个人不太懂最后面一行没看懂，就是：pw=pv;pww=TRUE;/pw=pv+w,书本也没有对其路径的输出做处理，我也没有深究下去，而是参考别的资料采用另一种方法来处理（不过都是差不多的吧）。总的来说，个人觉得输出路径的函数PassPath()很经典。另外一开始看不懂书本上的算法就感觉好打击，后来就分析算法后面的运行情况，上机调试，慢慢的就基本明白了。算法实现后，就是要解决给用户的体验效果了，这个就不难，仅做简单处理，写了一个简单的SetName()函数（名字取得不太好，应该叫GetName()），然后选择适当的时候输出适当的话或城市名就行了。附录：（代码）头文件部分：#include#define INF 1000 /最大值无穷#define MAX_VERTEX_NUM 7 /最大顶点数typedef enum DG,DN,UDG,UDN GraphKind;/有向图，有网图，无向图，无网图typedef int InfoType;/ 弧相关信息类型/弧相关信息的指针typedef char VertexType; / 顶点数据类型typedef int VRType; / 顶点关系类型。对无权图，用0或者1表示是否相邻。对带权图，直接表示权值。typedef struct ArcCellVRType adj; / 顶点关系类型,对无权图，用0或者1表示是否相邻。对带权图，直接表示权值InfoType *info;/弧相关信息的指针AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix M;/邻接矩阵int vNum,eNum;/顶点数弧数GraphKind kind;MGraph;int CreateDN(MGraph &g)for(int i=0;iMAX_VERTEX_NUM;i+)for(int j=0;jMAX_VERTEX_NUM;j+)g.Mij.adj=INF;if(i=j)g.Mij.adj=0;g.M01.adj=100;g.M02.adj=200;g.M03.adj=200;g.M13.adj=50;g.M14.adj=150;g.M23.adj=100;g.M25.adj=150;g.M34.adj=100;g.M35.adj=350;g.M46.adj=150;g.M54.adj=400;g.M56.adj=500;g.vNum=g.eNum=MAX_VERTEX_NUM;char c = #;printf(有向网带权邻接矩阵为（#代表无穷大）：nn);printf( 广州 佛山 肇庆 珠海 深圳 南宁 香港n);for(int k=0;kg.eNum;k+)for(int l=0;lg.eNum;l+)if(g.Mkl.adj != 1000)printf(%5d,g.Mkl.adj);else printf(%5c,c);printf(n);printf(n);return 1;源文件部分：#include #includeShortestPath.hvoid SetName(int i)switch(i)case 0 : printf(广州);break;case 1 : printf(佛山);break;case 2 : printf(肇庆);break;case 3 : printf(珠海);break;case 4 : printf(深圳);break;case 5 : printf(南宁);break;case 6 : printf(香港); /输出路径函数，如a-d的最短路径途经c，而a-c的最短路径途经b,/那其实a-d的最短路径同时途经了b和c。而根据d只能得到一个i（k）/故只能求出c。现在也要求出b来，只能通过c来求，所以形成了递归。void PassPath(int p,int i,int v)int k = pi;if(k=v)return;/直达，无路径。PassPath(p,k,v);/递归调用SetName(k);printf(-);void ShortestPath(MGraph g,int v0)int const MAX = MAX_VERTEX_NUM;int SMAX;/S集-为1时意味着保存了最终v0到v的最短路径int DMAX;/最短距离int PathMAX;/若Pathi=j,表示v0-vi的最短距离的路径包含vj。/而且vj一直保持被更新状态，输出路径时就要用到递归。for(int v=0;vg.eNum;+v)/初始化Sv = -1;/S集里面设为空Dv = g.Mv0v.adj;/矩阵第一行（即v0到其他点的直接距离）赋给D;if(DvINF)Pathv = v0;/路径设为空else Pathv = -1;Dv0 = 0;Pathv0 = 0;Sv0 = 1;/v0加入S集/开始主循环，每次求得v0到其他顶点v的最短路径，并加v到S集for(int i=1;ig.eNum;i+)int v;int min = INF;/min保存当前所知离v0顶点最近的距离for(int w=0;wg.eNum;w+)if(Sw = -1)/w顶点不在S里if(Dwmin)v = w;/记下当前最短距离的位置min = Dw;/修改minSv = 1;/加入S集for(int w=0;wg.eNum;w+)if(Sw = -1 & (min + g.Mvw.adj Dw)Dw = min + g.Mvw.adj;/修改当前最短距离Pathw = v;/保存下途经路径，并随时更新/输出最短距离for(int i=0;ig.eNum;i+)if(Di=1000) printf(广州到);SetName(i);printf(的最短距离为：无穷大n);else printf(广州到);SetName(i);printf(的最短距离为：%dn,Di);/输出Pathprintf( path:);for(int i=0;ig.eN