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

《数据结构_图的最短路径实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验课程名称数据结构实验题目名称图的最短路径实现学生学院应用数学学院专业班级信息计算1班学号3114008104学生姓名陈辉腾指导教师刘志煌2016年6月13日图的最短路径实现14信计1班—陈辉腾—3114008104实验要求：广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。实验目的：进一步了解数据结构中对图的各种操作，以及求最短路径的算法。实验内容：编程求解上述题目（实验要求）思路：首先把图用带权邻接矩阵g表示出来（每

2、个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v的最短路径保存到D[v]，以及途经的一个最近新的路径保存Path[v]。最后输出D[v]以及Path[v]。构造领接矩阵代码如下（详细思路写在代码注释里面）：其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）数据类型定义：构造上述领接矩阵函数代码：运行结果如下：求最短距离和路径函数如下：其中，PassPath(Path,i,v0)函数实现如下：SetName(i)函数（根据矩阵的行列数i，获得对应

3、的城市名）实现如下：运行求解结果为：总结：一开始觉得图的好难，不过，确实很难啊，图比树复杂多了。其实还有一部分原因是自己对图比较陌生的缘故吧。对于这个求最短路径的算法的难点，个人觉得是在输出路径那里，巧妙的用到了递归。还有我觉得，怎么把巧妙的吧途经最短路径保存下来？处理这个问题我就觉得是一个难点，把这个问题处理的好，输出时就比较不用那么麻烦。书本是用一个二维数组p[][]和一个一维数组p[]来处理，两个数组名还一样，个人不太懂—>最后面一行没看懂，就是：p[w]=p[v];p[w][w]=TRUE;//p[w]=p[v]+[w],书本也没有

4、对其路径的输出做处理，我也没有深究下去，而是参考别的资料采用另一种方法来处理（不过都是差不多的吧）。总的来说，个人觉得输出路径的函数PassPath()很经典。另外一开始看不懂书本上的算法就感觉好打击，后来就分析算法后面的运行情况，上机调试，慢慢的就基本明白了。算法实现后，就是要解决给用户的体验效果了，这个就不难，仅做简单处理，写了一个简单的SetName()函数（名字取得不太好，应该叫GetName()），然后选择适当的时候输出适当的话或城市名就行了。附录：（代码）头文件部分：#include#defineINF100

5、0//最大值无穷#defineMAX_VERTEX_NUM7//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有网图，无向图，无网图}typedefintInfoType;//弧相关信息类型//弧相关信息的指针typedefcharVertexType;//顶点数据类型typedefintVRType;//顶点关系类型。对无权图，用0或者1表示是否相邻。对带权图，直接表示权值。typedefstructArcCell{VRTypeadj;//顶点关系类型,对无权图，用0或者1表示是否相邻。对

6、带权图，直接表示权值InfoType*info;//弧相关信息的指针}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixM;//邻接矩阵intvNum,eNum;//顶点数弧数GraphKindkind;}MGraph;intCreateDN(MGraph&g){for(inti=0;i

7、){g.M[i][j].adj=INF;if(i==j)g.M[i][j].adj=0;}}g.M[0][1].adj=100;g.M[0][2].adj=200;g.M[0][3].adj=200;g.M[1][3].adj=50;g.M[1][4].adj=150;g.M[2][3].adj=100;g.M[2][5].adj=150;g.M[3][4].adj=100;g.M[3][5].adj=350;g.M[4][6].adj=150;g.M[5][4].adj=400;g.M[5][6].adj=500;g.vNum=g.eNu

8、m=MAX_VERTEX_NUM;charc='#';printf("有向网带权邻接矩阵为（‘#’代表无穷大）：");printf("广州佛山肇庆珠海深圳南宁香港")