dijkstra与floyd方法求最短路径实验报告.doc

实验报告
实验名称
求最短距离及最短路线。
实验目的
掌握最短路径的基础知识，掌握求最短路径的方法。
（2）充分了解Dijkstra算法与Floyd算法的性质与原理。
（3）利用编程的方法求出一个无向图（有向图）中的最短路径。
实验内容与要求
①
②
③
④
⑤
⑥
⑦
⑧
4
5
2
6
1
7
8
3
9
3
2
6
12
16
18
求最短距离及最短路线。
1、用Dijkstra算法求从节点1到节点8的最短路，并用程序实现；
2、用Floyd算法求任意两点之间的最短路，并用程序实现；
3、程序实现所用语言不限；
实验原理与步骤
Dijkstra算法
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中包含了图的所有顶点。

实验步骤：
此程序使用了visualstudio2010进行编写，程序参考了《数据结构C++版》课本中的原有程序以及相关知识，并进行了一些改动。
建立一个classDis类，用来记录起点到每个顶点的最短路径的信息。
建立一个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<longlong>(begin))+"-->v"+to_string(static_cast<longlong>(i+1));
dis[i].value=arc[begin-1][i];
}
设置起点到起点的路径为0；
dis[begin-1].value=0;
接下来利用count计算剩余顶点的最短路径，temp用于保存当前dis数组中最小的下标，min记录当前的最小值；
把temp对应的顶点加入到已经找到的最短路径的集合中；
为防止内存泄漏，此处我们选择加入条件arc[temp][i]!=INT_MAX的方法；
不断更新最短路径和长度总和，直到算出最后结果；
使用一个check函数判断输入的顶点个数和边的条数是否是合法的。
在主函数中建立表类的一个对象，要求用户输入图的顶点、边、边的权值等信息，并使用建立的对象调用上面所写的函数。

Floyd算法
实验原理：
利用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]