下载文档原格式
实验报告
一、实验名称
求最短距离及最短路线。
二、实验目的
（1）掌握最短路径的基础知识，掌握求最短路径的方法。
（2）充分了解Dijkstra 算法与Floyd 算法的性质与原理。
（3）利用编程的方法求出一个无向图（有向图）中的最短路径。
三、实验内容与要求
求最短距离及最短路线。
1、用Dijkstra 算法求从节点1到节点8的最短路，并用程序实现；
2、用Floyd 算法求任意两点之间的最短路，并用程序实现；
3、程序实现所用语言不限；
四、实验原理与步骤
（一）Dijkstra 算法 ① ②
③ ④ ⑤ ⑥ ⑦
⑧ 4 5 2 6 1 7 8 3
9
3
2 6 111
1、实验原理：
Dijstra为了算出图中某点到其它点的最短路径，提出了按路径的长度递增次序，逐步产生最短路径的算法，被称为Dijstra算法。Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点s 的路径权重被赋为0 （dis[s] = 0）。若对于顶点s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s，然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。然后，又从dis 中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
2、实验步骤：
此程序使用了visual studio2010进行编写，程序参考了《数据结构C++版》课本中的原有程序以及相关知识，并进行了一些改动。
(1)建立一个class Dis类，用来记录起点到每个顶点的最短路径的信息。
(2)建立一个Graph_DG类，存放图的顶点和边数、存储图的邻接矩阵以及程序中使用到的
函数。
Graph_DG类中的主要函数：
①析构函数：用于初始化顶点数和边数。
②构造函数：用于释放程序中开辟的内存空间。
③check_edge_value函数：判断输入边的数据是否是合法的。
④creatGraph函数：创造一个新的图表。
⑤print函数：打印出图的邻接矩阵。
⑥Dijkstra函数：Dijkstra算法的具体实现（利用实验原理中的算法进行程序设计）。
⑦Print_path函数：打印出最小路径以及最小路径的长度。
关于表的输入、打印等函数此处不再赘述。下面主要叙述Floyd函数的建立：
①首先初始化dis数组并设置当前的路径；
for (i = 0; i < this->vexnum; i++) {
dis[i].path = "v" + to_string(static_cast
to_string(static_cast
dis[i].value = arc[begin - 1][i];
}
②设置起点到起点的路径为0；
dis[begin - 1].value = 0;
③接下来利用count计算剩余顶点的最短路径，temp用于保存当前dis数组中最小
的下标，min记录当前的最小值；
④把temp对应的顶点加入到已经找到的最短路径的集合中；
⑤为防止内存泄漏，此处我们选择加入条件arc[temp][i]!=INT_MAX的方法；
⑥不断更新最短路径和长度总和，直到算出最后结果；
(3)使用一个check函数判断输入的顶点个数和边的条数是否是合法的。
(4)在主函数中建立表类的一个对象，要求用户输入图的顶点、边、边的权值等信息，并使
用建立的对象调用上面所写的函数。
（二）Floyd算法
1、实验原理：
利用Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。同理，第k次更新时，如果”a[i][j]的距离”> “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”
a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成。
2、实验步骤：
本题与Dijkstra算法的程序大部分内容相似，仅有Floyd函数部分做了改动。同样的，此程序使用了visual studio2010进行编写，程序参考了《数据结构C++版》课本中的原有
程序以及相关知识。
(1)建立一个Graph_DG类，定义图的顶点和边数、存储图的邻接矩阵以及程序中使用到的函数。
Graph_DG类中的主要函数：
①析构函数：用于初始化顶点数和边数。
②构造函数：用于释放程序中开辟的内存空间。
③check_edge_value函数：判断输入边的数据是否是合法的。
④creatGraph函数：创造一个新的图表。
⑤Floyd函数：Floyd算法的具体实现（利用实验原理中的算法进行程序设计）。
⑥print函数：打印出图的邻接矩阵。
⑦Print_path函数：打印出最小路径以及最小路径的长度。
关于表的输入、打印等函数此处不再赘述。下面主要叙述Floyd函数的建立：
①两个for循环的作用是把矩阵D初始化为邻接矩阵的值，矩阵p的初值则为各个边
的终点顶点的下标。
for (i= 0; i< this->vexnum; i++) {
for (j=0; j< this->vexnum; j++) {
this->dis[i][j] = this->arc[i][j];
this->path[i][j] = j;
}
}
②三重循环的作用是计算每个点对的最短路径，在三重循环中进行不断更新D和P矩
阵的操作。
for (int m = 0;m
for (i = 0;i < this->vexnum; i++) {
for (j = 0; j< this->vexnum; j++) {
n=(dis[i][m]==INT_MAX||dis[m][j] == INT_MAX)?INT_MAX:(dis[i][m] +
dis[m][j]);
if (this->dis[i][j]>n) {
this->dis[i][j]=n;
this->path[i][j]=this->path[i][m];
