Floyd-Warshall 算法及其优化

今天是教师节，因而下午放假，有了些复习时间。上午挺强的，几个老师被我们用彩带一顿狂喷，有几个还被迫唱歌了。因为前方黑板被占（几个大字），有两个老师是站在后面上课的（后面有空黑板），这下我这类最后一排的有福了。不过后黑板平时无人使用，没放板擦、粉笔，两节课都是我主动到前面去拿来的。第一节是灵感突发，第二节我看没人接班，无奈，只得又去一趟。算是RP++吧。

好了，言归正传。Floyd-Warshall 算法解决了有向图中每对定点间最短路径的问题，时间O(V³)，空间O(V²)。适用条件是，换句话说限制是，不能有负权值环，当然还有，最多只能有一条从一个点到另一个点的弧（基本都是这样。不然，长的那个可以直接去掉，没用）。对于无向图，把一条边变成两条弧。尽管有负权值环时它不可用，但可以判断是否有负权值环，方法是再运行一次（不过代价不小）。

这是个动态规划算法，基本思想如下。如果顶点k在顶点i到顶点j的一条路径上，则称k为该路径的一个中间顶点。如果路径p是从i到j的最短路径且k是其中间顶点之一，则以k为界将该路径分成两段，每段都是最短路径。（不然的话会出来一个更短的。）相反，如果路径a, b分别是i->k, k->j的最短路径，将a和b合并起来的路径不一定是最短路径。为了得到最短路径，我们必须考察图中的所有顶点，以他们为中间顶点，合并起来才能是最短的。基于此，我们可以得到算法。用邻接矩阵表示图，算法如下（C++）。

for (int k=1;k<=n;++k)
  for (int i=1;i<=n;++i)
    if (ans[i][k] != _infty) //the one line optimization
      for (int j=1;j<=n;++j)
        ans[i][j]=min(ans[i][j], ans[i][k] + ans[k][j]);

那个仅一行的优化是我后加的，可以去掉。预处理时[i][i]为0，有弧的是权值，没有的是无穷大。_infty是预处理时当作无穷大的量。优化后的具体时间复杂度我一直没有做出来，总之松弛的界是Ω(VE)和O(V³)。这个算法极其简洁，我认为是最优美的算法。（其次是堆。）上述代码整合到程序中后，通过编译且运行正确。