欢迎来到天天文库
浏览记录
ID:39810958
大小:117.52 KB
页数:12页
时间:2019-07-11
《数据结构实验报告 最短路径》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验报告实验名称最短路径课程名称数据结构与算法实验
2、
3、专业班级:信息安全学号:姓名:实验六最短路径一、实验目的1.学习掌握图的存储结构2.学会编写求最短路径的算法二、实验内容1、实验题目编写代码实现Dijkstra生成最短路径的算法,其中要有完整的图的输入输出2、简单介绍图的存储:用邻接矩阵,这样会方便不少。邻接矩阵是一个二维数组,数组中的元素是边的权(一些数值),数组下标号为结点的标号。(1)例如二维数组中的一个元素M[5][6]的值为39,则表示结点5、6连接,且其上的权值为39。(2)用邻接矩阵存储图,对图的读写就简单了。因
4、为邻接矩阵就是一个二维数组,因此对图的读写就是对二维数组的操作。只要能弄清楚边的编号,就能把图读入了。用一对结点表示边(也就是输入的时候输入一对结点的编号)求最短路径的算法:求最短路径就是求图中的每一个点到图中某一个给定点(这里认为是编号为0的点)的最短距离。具体算法就是初始有一个旧图,一个新图。开始的时候旧图中有所有的结点,新图中初始为只有一个结点(源点,路径的源头)。整个算法就是不停的从旧图中往新图中添加点,直到所有的点都添加到新图中为止。要实现这个算法,除了用二维数组保存图,还需要使用到两个辅助的数组数组find[N]:此数
5、组是用来表示标号对应的结点是否已经被添加到新图中(因为只有旧图中的点我们才需要添加到新图中,并且只有旧图中点到源点的距离,我们才需要进行更新)其中N为图中结点的个数。数组distance[N]:此数组记录图中的点到源点的距离。这个数组里面存放的值是不断进行更新的。其中N为图中结点的个数。3、程序简单模板只是参考,不需要照着这个来写//最短路径#ifndefMYGRAPH_H_#defineMYGRAPH_H_classMyGraph{public:voidreadDirectedGraph();MyGraph(intsize);/
6、/构造函数中设置图的大小,分配空间voidwriteGraph();voidshortPath(intsource);//求最短路径protected:private:int**m_graph;//用二维数组保存图intm_size;//图的大小};#endif///////////////////////////////////////////////////////////////////////构造函数中设置图的大小,分配空间MyGraph::MyGraph(intsize){inti,j;m_size=size;//给图分
7、配空间m_graph=newint*[m_size];for(i=0;i#include#include#include#includeusingnamespacestd;structprimnode{pu
8、blic:charbegvex;charendvex;intlowcost;};structadknode{intdist;//最近距离charway[50];//顶点数组intnodenum;//经过的顶点数};classMgraph//邻接矩阵储存结构{public:Mgraph(){}~Mgraph(){}voidCreatMGraph();voidDFS(int);//用递归实现voidDFS1(int);//非递归voidBFS(int);voidprint();voidprim();intmini();intlow()
9、;//最短距离函数的辅助函数intLocateVex(char);voidkruskal();voidDijkstra();voidFloyd();private:intnumber;//顶点数目intarcnum;//边的数目charvexs[50];intarcs[50][50];intvisited[50];//便利时的辅助工具primnodecloseedge[50];//primadknodedist[50];//最短路径intD[20][20];//floyd算法距离intP[20][20][20];//floyd算法
10、路径};intMgraph::LocateVex(chars){for(inti=0;i
此文档下载收益归作者所有