最短路————无垠荒野的明灯

· · 个人记录

在春节前集训最后一天，不想写题的毛毛来到他的博客左思右想最后挑了这几天他最熟的最短路来（水）写一篇博客

最短路

最短路这种东西相信大家都很熟悉了，不需要再过多细讲，那这篇博客就到此结束，谢谢，那姑且还是先分别介绍一下吧

Floyed算法

应该是很多人初学的最短路算法，但虽然基础，floyed可是多源最短路算法，在许多题有着不可替代的作用，而floyed最常见的就是以下的五行代码

for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++){
        if( f[i][k]+f[k][j]<f[i][j] )f[i][j]=f[i][k]+f[k][j];
      }//没错这就是floyed了，就没了

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程

到这里我们已经知道，Floyd算法就是一个利用其它点进行中转来求最短路的步骤。简单易懂，这里推两道题让大家熟悉Floyed：P1364 医院设置 ， P1522 [USACO2.4]牛的旅行 Cow Tours，这两题都是标准的Floyed模板

然后，很多人会选择背下上面的五行代码，在考试时直接默写，这好吗？这不好，有时候，合理运用Floyed的本质思想：通过一个中转点来修改其他点的最短路，这种思想在一些题可以起到别样的作用，具体请看P1119 灾后重建

Floyed就先讲到这，下一位

Dijkstra算法