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);/求最短路径protect
4、ed:private:int *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#include #include #include #include using namespace std;struct primnodepublic:char begvex;char endvex;int lowcost;struct adknodeint dist;/最
5、近距离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();int low();/最短距离函数的辅助函数int LocateVex(char);void kruskal();void Dijkstra();void Floyd();private:int number;
6、/顶点数目int arcnum;/边的数目char vexs50;int arcs5050;int visited50;/便利时的辅助工具primnode closeedge50;/prim adknode dist50;/最短路径int D2020;/floyd 算法距离int P202020;/floyd 算法路径; int Mgraph:LocateVex(char s)for(int i=0;inumberarcnum;coutvexsi;for(i=0;ivex1vex2m;i=LocateVex(vex1);j=LocateVex(vex2);arcsij=m;arcsji=m;v
7、oid Mgraph:DFS(int i=0)/用递归实现int j;cout“;visitedi=1;for (j=0;j st;st.push(i);while(!st.empty()int j=st.top();st.pop();cout“;visitedj=1;for(int k=0;k de;de.push_back(i);cout“;visitedi=1;while(!de.empty()int k=de.front();for(int j=0;j“;visitedj=1;de.push_back(j);de.pop_front();int Mgraph:mini()static
8、int i;int min=0;for (int j=0;jcloseedgej.lowcost)min=j;i=min;coutu;int i=LocateVex(u);visitedi=1;for(int j=0;ju;int i=LocateVex(u);visitedi=1;for (int j=0;jdistn.dist)distance=distn.dist;min=n;int m=min;visitedm=1;for (n=0;n“;for (int p=0;p“;coutvexsnendl;else coutvexsi“到“vexsn“没有通路“endl; void Mgraph:Floyd()int i,j,m,n;for ( i=0;inumber;i+)
