实 验 报 告 实验名称 最短路径 课程名称 数据结构与算法实验 | | 专业班级：信息安全 学 号： 姓 名： 实验六 最短路径 一、实验目的 1.学习掌握图的存储结构 2.学会编写求最短路径的算法 二、实验内容 1 、实验题目 编写代码实现 Dijkstra 生成最短路径的算法，其中要有完整的图的输入输出 2 、简单介绍 图的存储：用邻接矩阵，这样会方便不少。 邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。 （1）例如二维数组中的一个元素 M[5][6]的值为 39，则表示结点 5、6 连接，且其上的权值为 39。 （2）用邻接矩阵存储图，对图的读写就简单了。因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。只要能弄清楚边的编号，就能把图读入了。 用一对结点表示边（也就是输入的时候输入一对结点的编号） 求最短路径的算法： 求最短路径就是求图中的每一个点到图中某一个给定点（这里认为是编号为 0 的点）的最短距离。 具体算法就是初始有一个旧图，一个新图。开始的时候旧图中有所有的结点，新图中初始为只有一个结点（源点，路径的源头）。整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。 要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组 数组 find[N]：此数组是用来表示标号对应的结点是否已经被添加到新图中（因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点的距离，我们才需要进行更新）其中 N 为图中结点的个数。 数组 distance[N]：此数组记录图中的点到源点的距离。这个数组里面存放的值是不断进行更新的。其中 N 为图中结点的个数。 3 、程序简单模板 只是参考，不需要照着这个来写 //最短路径 #ifndef MYGRAPH_H_ #define MYGRAPH_H_ class MyGraph { public: void readDirectedGraph(); MyGraph(int size);//构造函数中设置图的大小，分配空间 void writeGraph(); void shortPath(int source);//求最短路径 protected: private: int **m_graph;//用二维数组保存图 int m_size;//图的大小 }; #endif ///////////////////////////////////////////// //////////////////////// //构造函数中设置图的大小，分配空间 MyGraph::MyGraph(int size) { int i,j; m_size=size; //给图分配空间 m_graph=new int* [m_size]; fo...
