欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

和小哥哥一起刷洛谷(8) 图论之Floyd“算法”

程序员文章站 2022-03-02 18:09:07
...

关于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的最短路<目前得出从i到j的最短路): 更新i到j最短路

别问我复杂度,看看这华丽的三重循环就知道了
大家也许注意到我标题中用的是带引号的“ 算法 ”。其实,我觉得真正意义上,这不算一个算法,之能称之为一种“暴力”,尤其其时间复杂度为恐怖的 N^3

这样的一种“算法”,美曰其名叫“重机枪” (丑曰其名叫“全国中小学生宇宙超级无敌大枚举”)

转载于:https://www.cnblogs.com/BlogE/p/luogu_day8.html