实验报告

课程名称 《算法分析与设计》
实验日期 2021年 3月15日
实验名称 最短路Floyd算法和Dijkstra算法
实验地点 勤园13-208

1.问题

[描述算法问题，首选形式化方式（数学语言），其次才是非形式化方式（日常语言）]

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵）。

问题

若∃n个点，m条单向边，设dis[i][j]为i点到j点的距离，使用Floyd算法求各点之间的最短距离，并绘制矩阵。

实例

存在4个点，如上图各点之间存在单向路径，使用Floyd算法求取各点之间的最短距离并绘制矩阵。

对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

问题

若∃n个点，m条单向边，设dis[i][j]为i点到j点的距离，使用Dijkstra算法求顶点a到顶点h的最短路径。

实例

存在4个点，如上图各点之间存在单向路径，使用Dijkstra算法求顶点a到顶点h的最短路径。

2.解析

[问题的理解和推导，可用电子版直接在此编写，也可用纸笔推导，拍照嵌入本文档]

Floyd算法

Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。对于每一对顶点<u,v>查询是否存在顶点w使得u到w再到v的距离比原本距离更近，并进行状态转移，更新矩阵。在算法问题中，首先绘制路径矩阵记录点与点之间的距离，然后从任一点出发，对于每一对顶点进行查询，设dis[i][j]为i到j的最短距离，那么比较dis[i][j]和dis[i][k]+dis[k][j]即可完成路径压缩，最终实现目标。

具体步骤

1.初始化路径矩阵，所有两点之间的距离为边的权值，如果两点之间没有边相连，则权值无穷大。
2.对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短，如果是则更新它。

Dijkstra算法

Dijkstra算法采用贪心策略，使用数组dis保存初始路径矩阵，数组len来保存源点到各个顶点的最短距离（len[i] = 0）,数组path记录路径。从len数组选择最小值，则该值为当前源点到其他点的最短路径，并且把该点加入到path中，然后对其他点进行路径压缩，最后重复步骤。

具体步骤

1.初始化路径矩阵，所有两点之间的距离为边的权值，如果两点之间没有边相连，则权值无穷大。
2.从len数组选择最小值，则该值为当前源点到其他点的最短路径，并且把该点加入到path中，然后对其他点进行路径压缩。
3.重复步骤2。

3.设计

[核心伪代码]

Floyd算法

设E(u,v)为u点到v点的距离；
For(每一个点k)
	For（每一个点i）
		For（每一个点j）
 			IF（E（i，j）>E（i，k）+E（k，j））
				E（i，j）=E（i，k）+E（k，j）；

Dijkstra算法

MST = {s};
while (1) {
	V = 未收录顶点中距离最小者;
	if ( V不存在 )
		break;
	else
		将V收录进MST;
	V被收录；
	for ( 每个点 W )
		if ( W未被收录 )
			if ( 最短路径到W的距离 <最短路径到V的距离 +V到W的距离 ){
				最短路径到W的距离 <最短路径到V的距离 +V到W的距离 ；
				记录W的前一个点位V；
				}
}

4.分析

[算法复杂度推导]

Floyd算法

遍历每一个点，总共三层循环，总复杂度为O（N^3）。

Dijkstra算法

每次找边的时候需要枚举所有点，并且将最小的出边更新，时间复杂度为O(N)，共需要重复进行n-1次，找n-1个点，总复杂度为O(N^2)。

5.源码

[github源码地址]
链接: github源码地址