Floyd算法

　

floyd算法

Floyd最短路算法

当初学这个算法的时候，都说是DP思想……但是当时学的匆匆，具体是怎么个DP法确实不大清楚，但是理解这个东西，一旦出了偏差，代码就会莫名爆炸……

其实对于最短路的算法，最重要的步骤其实就是松弛，比如dijkstra算法，贪心策略就是，每次让到源点距离最近的那个点，去松弛其他的点。

而弗洛伊德算法的基操也是松弛操作，但和单源最短路径的只松弛源点到其他点的距离不同，Floyd算法每次选取一个点，去松弛其他任意两点的最短路径

具体过程可以描述为这样：

整个过程可分为n个阶段，n为图中点的个数

在阶段 $k$k，对于$DP\left[k\right]\left[i\right]\left[j\right]$DP[k][i][j]，我们可以理解为，已经考虑了前 $k$k 个点并使用了第 $k$k 个点做松弛后，点$i$i到点$j$j的最短距离

则有转移方程：

$DP\left[k\right]\left[i\right]\left[j\right]=min\left(DP\right[k\left]\right[i\left]\right[j],DP[k-1\left]\right[i\left]\right[k]+DP[k-1\left]\right[k\left]\right[j\left]\right)$DP[k][i][j]=min(DP[k][i][j],DP[k−1][i][k]+DP[k−1][k][j])

当然，目前看到的算法大多是$DP\left[i\right]\left[j\right]=min\left(DP\right[i\left]\right[j],DP[i\left]\right[k]+DP[k\left]\right[j\left]\right)$DP[i][j]=min(DP[i][j],DP[i][k]+DP[k][j])，也就是经过了降维。因为对于$DP\left[k\right]\left[i\right]\left[j\right]$DP[k][i][j]，依赖的历史状态只有 $DP[k-1]\left[i\right]\left[k\right]$DP[k−1][i][k] 和 $DP[k-1]\left[k\right]\left[j\right]$DP[k−1][k][j]，如果我们进行降维，只要保证在更新$DP\left[k\right]\left[i\right]\left[j\right]$DP[k][i][j]时，$DP[k-1]\left[i\right]\left[k\right]$DP[k−1][i][k] 和 $DP[k-1]\left[k\right]\left[j\right]$DP[k−1][k][j]没有被第K阶段更新过即可。

而只有当 $k=i$k=i 或 $k=j$k=j 时，$DP\left[i\right]\left[j\right]=min\left(DP\right[i\left]\right[j],DP[i\left]\right[k]+DP[k\left]\right[j\left]\right)$DP[i][j]=min(DP[i][j],DP[i][k]+DP[k][j])中依赖的两个历史状态可能被第K阶段更新，但是……$k=i$k=i 或 $k=j$k=j的情况，其实就等价于并没有引入第三点，也就是单纯的两点间距离(比如$k=i$k=i, 则 $DP\left[i\right]\left[j\right]=min\left(DP\right[i\left]\right[j],DP[i\left]\right[i]+DP[i\left]\right[j]=DP[i\left]\right[j\left]\right)=DP\left[i\right]\left[j\right],$DP[i][j]=min(DP[i][j],DP[i][i]+DP[i][j]=DP[i][j])=DP[i][j],) ，所以即使降了维，算法还是正确的。

既然K表示状态，所以理应在最外层循环……不要学我这个傻傻的把K写在最内层还对程序WA表示一脸懵逼的傻X

code

for(k = 0; k < n; ++ k) { 
	for(i = 0; i < n; ++ i) {
		for(j = 0; j < n; ++ j) {
			if(DP[i][j] > (DP[i][k] + DP[k][j])) {
                 DP[i][j] = DP[i][k] + DP[k][j];
                 path[i][j] = k;//顺便可以记录路径
			}
		}
	}
} 

文章最后发布于: 2018-10-19 23:24:50

相关阅读

三分钟了解协同过滤算法

计算用户/物品相似度，以相似度作为权重，对不同物品进行评分预测，从而实现物品。什么是协同过滤先举个生活中的场景，你想听歌却不知道

克鲁斯卡尔算法(Kruskal算法)求最小生成树

get到一个介绍克鲁斯卡尔算法最通俗易懂的文章，分享一下，如有侵权，请联系博主删除 求最小生成树之普里姆算法。该算法从顶点的角度为

带你搞懂决策树算法原理

一、决策树是什么？ 顾名思义，决策树是由一个个“决策”组成的树，学过数据结构的同学对树一定不陌生。决策树中，结点分为两种，放“决策

贪心算法

贪心算法 制定贪心策略，每次仅考虑局部最优解(贪心策略下)，而不是从全局上来考虑最优解，所以最终的结果是通过局部最优解近似全局

【代码实现】匈牙利算法

之前讲了导弹时，dalao（CJJ）把匈牙利也讲解了，我怕有些人不是很懂，我也来讲解一下。我们正经点，不要像“剩男剩女的大潮”之类的我还是按