关于floyd
floyd是一种可以计算图中所有端点之间的最短的“算法”,其伪代码如下:
for(所有起点i) for(所有终点j) 如果i=j: i到j最短路设为0 如果i与j相连: i到j最短路设为已知i到j的距离 如果都不满足: i到j距离设为无限for(枚举所有中间点k) for(枚举所有起点i) for(枚举所有终点j) 如果(从i到k的最短路+从k到j的最短路
别问我复杂度,看看这华丽的三重循环就知道了
N^3
。 这样的一种“算法”,美曰其名叫“重机枪” (丑曰其名叫“全国中小学生宇宙超级无敌大枚举”) 。