数据结构实验报告-最短路径

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;i<m_size;i+)m_graphi=new intm_size;for (i=0;i<m_size;i+)for(j=0;j<m_size;j+)m_graphij=INT_MAX;三 、实验代码#include<iostream>#include <iomanip

5、>#include <stack>#include <deque>#include <fstream>using namespace 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

6、 );/用递归实现 void DFS1(int );/非递归 void BFS(int ); void print(); void prim(); int mini(); 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 adk

7、node dist50;/最短路径 int D2020;/floyd算法距离 int P202020;/floyd算法路径; int Mgraph:LocateVex(char s) for(int i=0;i<number;i+) if (vexsi=s) return i; return -1;void Mgraph:print() cout<<"顶点为： " for(int k=0;k<number;k+) cout<<vexsk; cout<<endl; for(int i=0;i<number;i+) for(

8、int j=0;j<number;j+) cout<<setw(6)<<left<<arcsij<<" " cout<<endl; for(int m=0;m<number;m+) cout<<visitedm; cout<<endl;void Mgraph:CreatMGraph()/图的邻接矩阵储存结构 char vex1,vex2; int i,j,k,m; cout<<"请输入定点数，边数："<<endl; cin>>

9、;number>>arcnum; cout<<"请输入顶点（字符串类型）："<<endl; for(i=0;i<number;i+) cin>>vexsi; for(i=0;i<number;i+) for(j=0;j<number;j+) arcsij=1000; for(k=0;k<arcnum;k+) cout<<"请输入边的两个顶点及边的权值： "<<endl; cin>>vex1>>vex2>>m; i=Locat

10、eVex(vex1); j=LocateVex(vex2); arcsij=m; arcsji=m; void Mgraph:DFS(int i=0)/用递归实现 int j; cout<<vexsi<<"->" visitedi=1; for (j=0;j<number;j+) if(!(arcsij=1000)&&!visitedj) DFS(j); void Mgraph:DFS1(int i=0)/非递归 stack<int> st; st.push(i); while(!st.empty() int

11、j=st.top(); st.pop(); cout<<vexsj<<"->" visitedj=1; for(int k=0;k<number;k+) if(!(arcsjk=1000)&&!visitedk) st.push(k); void Mgraph:BFS(int i=0)/广度优先遍历 deque<int> de; de.push_back(i); cout<<vexsi<<"->" visitedi=1; while(!de.empty() in

12、t k=de.front(); for(int j=0;j<number;j+) if(arcskj!=1000&&!visitedj) cout<<vexsj<<"->" visitedj=1; de.push_back(j); de.pop_front(); int Mgraph:mini() static int i; int min=0; for (int j=0;j<number;j+) if(!visitedj) if (closeedgemin.lowcost>closeedgej.lowcost

13、) min=j; i=min; cout<<"包括边("<<closeedgei.begvex<<","<<closeedgei.endvex<<")" return i;void Mgraph:prim() char u; cout<<"请输入起始顶点："<<endl; cin>>u; int i=LocateVex(u); visitedi=1; for(int j=0;j<number;j+) closeed

14、gej.begvex=u; closeedgej.endvex=vexsj; closeedgej.lowcost=arcsij; for (int m=1;m<number;m+) int n=mini(); visitedn=1; closeedgen.lowcost=1000; for (int p=0;p<number;p+) if(!visitedp) if(arcspn<closeedgep.lowcost) closeedgep.lowcost=arcspn; closeedgep.begvex=vexsn; void Mgraph:kruskal() int

15、a,b,k=0; int min=1000; int arcs12020; for (int m=0;m<number;m+) visitedm=m;/每一个顶点属于一颗树 for (int i=0;i<number;i+) for(int j=0;j<number;j+) arcs1ij=arcsij; while (k<number-1) min=1000; for (int i=0;i<number;i+) for (int j=0;j<number;j+) if (arcs1ij<min) a=i; b=j; min=arcs1ij; if (

16、visiteda!=visitedb) cout<<"包括边("<<vexsa<<","<<vexsb<<")" k+; for (int n=0;n<number;n+) if (visitedn=visitedb) visitedn=visiteda; else arcs1ab=arcsba=1000; void Mgraph:Dijkstra() cout<<"请输入起始点"<<endl; char u; cin>

17、>u; int i=LocateVex(u); visitedi=1; for (int j=0;j<number;j+) distj.dist=arcsij; distj.nodenum=0; for (j=1;j<number;j+) int distance=1000; int min=0; for (int n=0;n<number;n+) if(!visitedn) if (distance>distn.dist) distance=distn.dist; min=n; int m=min; visitedm=1; for (n=0;n<numbe

18、r;n+) if(!visitedn) if(distm.dist+arcsmn)<distn.dist) distn.dist=distm.dist+arcsmn; distn.nodenum=0; for (int x=0;x<distm.nodenum;x+) distn.wayx=distm.wayx; distn.nodenum+; distn.waydistn.nodenum+=vexsm; /输出功能 for (int n=0;n<number;n+) if (n!=i) if(distn.dist<1000) cout<<vexsi<&

19、lt;"到"<<vexsn<<"的最近距离为："<<distn.dist<<endl; cout<<"经过的顶点为："<<vexsi<<"->" for (int p=0;p<distn.nodenum;p+) cout<<distn.wayp<<"->" cout<<vexsn<<endl; else cout<<vexsi<&

20、lt;"到"<<vexsn<<"没有通路"<<endl; void Mgraph:Floyd() int i,j,m,n; for ( i=0;i<number;i+) for ( j=0;j<number;j+) for (m=0;m<number;m+) Pijm=0; for ( i=0;i<number;i+) for ( j=0;j<number;j+) Dij=arcsij; if(Dij<1000) Piji=1; Pijj=1; for ( i=0;i<number;i+) for ( j=0;j<number;j