《数据结构实验报告（最短路径）》由会员分享，可在线阅读，更多相关《数据结构实验报告（最短路径）（12页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告 实验名称 最短路径 课程名称 数据结构与算法实验 | 专业班级：信息安全 学 号： 姓 名：实验六 最短路径一、实验目的1.学习掌握图的存储结构2.学会编写求最短路径的算法二、实验内容1、实验题目编写代码实现Dijkstra生成最短路径的算法，其中要有完整的图的输入输出2、简单介绍图的存储：用邻接矩阵，这样会方便不少。邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。（1）例如二维数组中的一个元素M56的值为39，则表示结点5、6连接，且其上的权值为39。（2）用邻接矩阵存储图，对图的读写就简单了。因为邻接矩阵就是一个二维数组，因此对图的读写就是
2、对二维数组的操作。只要能弄清楚边的编号，就能把图读入了。用一对结点表示边（也就是输入的时候输入一对结点的编号）求最短路径的算法：求最短路径就是求图中的每一个点到图中某一个给定点（这里认为是编号为0的点）的最短距离。具体算法就是初始有一个旧图，一个新图。开始的时候旧图中有所有的结点，新图中初始为只有一个结点（源点，路径的源头）。整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组数组findN：此数组是用来表示标号对应的结点是否已经被添加到新图中（因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点
3、的距离，我们才需要进行更新）其中N为图中结点的个数。数组distanceN：此数组记录图中的点到源点的距离。这个数组里面存放的值是不断进行更新的。其中N为图中结点的个数。3、程序简单模板只是参考，不需要照着这个来写/最短路径#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraphpublic:void readDirectedGraph();MyGraph(int size);/构造函数中设置图的大小，分配空间void writeGraph();void shortPath(int source);/求最短路径protected:private:int
4、 *m_graph;/用二维数组保存图int m_size;/图的大小;#endif/ /构造函数中设置图的大小，分配空间MyGraph:MyGraph(int size)int i,j;m_size=size;/给图分配空间m_graph=new int* m_size;for (i=0;im_size;i+)m_graphi=new intm_size;for (i=0;im_size;i+)for(j=0;jm_size;j+)m_graphij=INT_MAX;三 、实验代码#include#include #include #include #include using namesp
5、ace std;struct primnodepublic: char begvex; char endvex; int lowcost;struct adknode int dist;/最近距离 char way50;/顶点数组 int nodenum;/经过的顶点数;class Mgraph/邻接矩阵储存结构public: Mgraph() Mgraph() void CreatMGraph(); void DFS (int );/用递归实现 void DFS1(int );/非递归 void BFS(int ); void print(); void prim(); int mini()
6、; int low();/最短距离函数的辅助函数 int LocateVex(char); void kruskal(); void Dijkstra(); void Floyd();private: int number;/顶点数目 int arcnum;/边的数目 char vexs50; int arcs5050; int visited50;/便利时的辅助工具 primnode closeedge50;/prim adknode dist50;/最短路径 int D2020;/floyd算法距离 int P202020;/floyd算法路径; int Mgraph:LocateVex(
7、char s) for(int i=0;inumber;i+) if (vexsi=s) return i; return -1;void Mgraph:print() cout顶点为： ; for(int k=0;knumber;k+) coutvexsk; coutendl; for(int i=0;inumber;i+) for(int j=0;jnumber;j+) coutsetw(6)leftarcsij ; coutendl; for(int m=0;mnumber;m+) coutvisitedm; coutendl;void Mgraph:CreatMGraph()/图的邻接
8、矩阵储存结构 char vex1,vex2; int i,j,k,m; cout请输入定点数，边数：numberarcnum; cout请输入顶点（字符串类型）：endl; for(i=0;ivexsi; for(i=0;inumber;i+) for(j=0;jnumber;j+) arcsij=1000; for(k=0;karcnum;k+) cout请输入边的两个顶点及边的权值： vex1vex2m; i=LocateVex(vex1); j=LocateVex(vex2); arcsij=m; arcsji=m; void Mgraph:DFS(int i=0)/用递归实现 int
9、j; coutvexsi; visitedi=1; for (j=0;jnumber;j+) if(!(arcsij=1000)&!visitedj) DFS(j); void Mgraph:DFS1(int i=0)/非递归 stack st; st.push(i); while(!st.empty() int j=st.top(); st.pop(); coutvexsj; visitedj=1; for(int k=0;knumber;k+) if(!(arcsjk=1000)&!visitedk) st.push(k); void Mgraph:BFS(int i=0)/广度优先遍历
10、deque de; de.push_back(i); coutvexsi; visitedi=1; while(!de.empty() int k=de.front(); for(int j=0;jnumber;j+) if(arcskj!=1000&!visitedj) coutvexsj; visitedj=1; de.push_back(j); de.pop_front(); int Mgraph:mini() static int i; int min=0; for (int j=0;jcloseedgej.lowcost) min=j; i=min; cout包括边(closeedg
11、ei.begvex,closeedgei.endvex); return i;void Mgraph:prim() char u; cout请输入起始顶点：u; int i=LocateVex(u); visitedi=1; for(int j=0;jnumber;j+) closeedgej.begvex=u; closeedgej.endvex=vexsj; closeedgej.lowcost=arcsij; for (int m=1;mnumber;m+) int n=mini(); visitedn=1; closeedgen.lowcost=1000; for (int p=0;pnumber;p+) if(!visitedp) if(arcspncloseedgep.lowcost) closeedgep.lowcost=arcspn; closeedgep.begvex=vexsn; void Mgraph:kruskal() int a,b,k=0; int min=1000; int arcs12020; for (int m=0;mnumber;m+) visitedm=m;/每一
