spfa算法

spfa的思路异常地顺（可能是因为我之前写错的dijkstra有一点相似），简直就是bfs的翻版。做好初始化（起点入队，除起点外的距离无穷大）后，循环同样是：

队首出队；
对于队首的每一个邻居，如有更小的距离：更新距离，并且如果其现在不在队列里，就入队。
也就是说，每一个顶点是可以多次入队的，只要它的祖先有更新，它就也跟着更新，它指向的儿子们也更新，就这样昏天黑地，直到没有动静，队列为空，就结束了。

优点除了极其好写之外，相比于dijkstra不能处理有负权的边，spfa是可以的，只要有向加权图G不存在负权回路，即最短路径一定存在，就可以使用。

至于复杂度，我有点搞不清楚，据说，最差退化到V * E, 但在一般情况下还是很好的，据说是两到三个E。

代码还是和之前的接口一致了，需要什么再添嘛：

int spfa(int from, int to){
    int dist[N], queue[5 * N], v, newDist;
    bool inq[N] = {0};

    int start = 0, end = 1;
    queue[0] = from;
    inq[from] = true;
    for(int i = 0; i < N; i ++) dist[i] = 1<<30;
    dist[from] = 0;

    while(end > start){
        v = queue[start ++];
        inq[v] = false;
        for(int i = 0; i < N; i ++){
            if(graph[v][i]){
                newDist = dist[v] + graph[v][i];
                if(newDist < dist[i]){
                    dist[i] = newDist;
                    if(! inq[i]){
                        queue[end ++] = i;
                        inq[i] = true;
                    }
                }
            }
        }
    }
    for(int i = 0; i < N; i ++) printf("%d ", dist[i]);
    return dist[to];
}

floyd算法

人生导师说这个比spfa还简单，骗鬼呢，代码是简单到让人怀疑人生，但是看上去很难想通，这个怎么会可以，做到后面的时候难道不会漏掉什么更新吗？

核心代码只有下面的几行：

int floyd(){
    //初始化
    int dist[N][N], newDist;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            dist[i][j] = (graph[i][j]? graph[i][j]: 1<<29);
            if(i == j) dist[i][j] = 0;
        }
    }

    //floyd
    for(int k = 0; k < N; k ++){
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++){
                newDist = dist[i][k] + dist[k][j];
                if(newDist < dist[i][j]) dist[i][j] = newDist;
            }
        }
    }

    //打印略
}

不同于前面两种算法的是，floyd可以求“多源最短路径”，也就是所有点对间的距离都求出来。

流程可以这样理解：

如果先规定两点 a, b 之间不能经过第三点，此时的dist[][]就由图的连边、无穷、0组成，也正是初始化的结果。
规定 a, b 之间可以经过点 0, 那么所有点对间的距离都要再算一遍，是不是有 a -> 0 -> b 的距离小于原先 a -> b 的距离，也就是比较dist[i][j]和dist[i][0] + dist[0][j]，取小的。内部的两层循环就是在做这个
再规定点 1 也可以被经过，那么就在原来的基础上，再比较dist[i][j]和dist[i][1] + dist[1][j]。
再依次放宽条件，使得 2、3、4……N - 1 可以被经过。最外层循环是在做这个。

上面只是笼统的说法，每一步到底在干什么并没有说清楚，虽然很多博客也就写到这里为止，欢天喜地地说只有这么几行太爽啦。这个算法写得太简洁，以至于我很容易觉得，好像每一步都是从头开始的循环，然后满脑子疑惑：“如果最短路不是简单的对于某一个 k 的 i -> k -> j，而是 i -> k1 -> k2 -> k3 -> j，这个算法到底有考虑这种情况吗？又是怎样在每个循环中做一步，以至于到结束后，能表示这样的结果呢？”

一定要扭转思想的是，这是一个dp，实际上，外层 k 的每一次循环，都是在前一次计算结果的基础上进行的。也就是说，在 k 为某值的时候，我们看到的不是从 i 到 j 中间只经过 k 的最短路径长度，而是从 i 到 j 中间可以经过0,1,2,...k 的最短路径长度。

某大神的博客证明了此算法的正确性。我更喜欢知乎问题“Floyd算法为什么把k放在最外层？”下 @赵轩昂和 @m00nlight 这两个回答结合起来的样子。先将其理解为三维数据dist[i][j][k]，弄清楚状态转移方程，再简化为状态 k - 1和状态 k 两个二维数组，再理解在一个二维数组中为什么新值旧值混用并不影响结果的正确性。

最后默念：这丫是个dp，不是个单纯的循环。