Floyd

代码简洁,三层循环,理解起来也很简单当然靠背诵也没什么问题,只要记住k在外面就万事大吉.
实际上,这是一个动态规划的代码awa
这个dp是这样的
首先我们拿到了两个点i,j
然后这两个点之间的最短路,一定是i,j之间经过了点k1,k2,k3……的来的当然直接i到j是最小也有可能.
所以说,我们要做的就是将这些k找出来.
当我们用k号节点作为中转节点的时候
ij的距离就可以更新为

min{dis[i][j],dis[i][k]+dis[k][j]}

也就是将一段距离转化为两段距离的和
然后我们只需要将中间节点k枚举一遍

for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dis[i][j]=min{dis[i][j],dis[i][k]+dis[k][j];
Last modification:April 12th, 2020 at 07:36 am
如果觉得我的文章对你有用,请随意赞赏