Floyed

Floyed(插点法)

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

在开始之前我们需要对一些图进行分类

图按照权值可以分为有权和无权

什么是有无权？

权值代表了图中任意两个结点之间的距离

无权说明两点之间的距离为1，而有权距离因题而议

按照方向可以定义为无向图和有向图

无向代表了从图上某一点到达另一点和往返到达距离都是相同的

而有向则恰恰相反，a -> b 和 b -> a之间的距离是不同的

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

步骤

第一步

首先我们需要对二维数组进行初始化

初始化的值为无穷代表任意两个点之间是无法到达的，需要特殊处理对角线上的值即g[i][i]为0，因为自己到自己之间没有距离

第二步

根据输入的值，构建树的结构，将从a - > b即g[a][b]和g[b][a]进行填充二维数组

第三部

参考大佬已经画好的图，本蒟蒻借用一下，参考地址

无向图邻接矩阵

开始设置中转点，比较是否经历中转点更好

模版代码

for(int k = 1;k <= n;k++) {
		for(int i = 1;i <= n;i++) {
				for(int j = 1;j <= n;j++) {
						if(g[i][j] > g[i][k] + g[k][j]) {
              	g[i][j] = g[i][k] + g[k][j]; //取更小的路径和
            }
				}
		}
}

如果不想设置自己作为中转点的话，我们需要对k = i,j = k进行特殊判断

有向图邻接矩阵

相比于无向图来说，我们需要新建立一个数组主要是用来记录结点跳动过程

如何初始化path数组呢？

我们可以设置path数组中的值都为-1

如果a结点可以到b结点，那么我们将其初始化为a的值

接着遍历所有中转结点

根据最终推演出来的临界矩阵，我们可以从中获取到两点之间最短路径的值以及，以及是如何走到

核心代码

for(int k = 1;k <= n;k++) {
		for(int i = 1;i <= n;i++) {
				for(int j = 1;j <= n;j++) {
						if(g[i][j] > g[i][k] + g[k][j]) {
								g[i][j] = g[i][k] + g[k][j];
								path[i][j] = k;
              	//本人认为是在不稳妥的话，可以修改成
             		//if(path[i][j] != -1) path[i][j] = min(path[i][j],k);
						}
				}
		}
}