全源最短路径——Floyd算法

• 问题引入
• 思路一览
• 算法原理
• 代码部分

问题引入

给出一个含有n个点，m条边的图，如何快速的给出任意两个点的最短路径

思路一览

这个，感觉没啥思路，可能能想到的最暴力的解法就是对每一个点进行dfs遍历，在遍历过程中更新，但是这样的做法肯定是时间复杂度爆炸的；因此还是老算法Floyd香，Floyd算法的有点递归的思想？感觉有点的，将a、b两个点的最短路径化为a和b的一个中继结点的最短路径的和，直到a、b结点直接相连

算法原理

像上面说的，两个点的最短路径有两种取法，一种是直接相连，一种是间接相连，即依靠其他点来更新最短距离；第一种好说，直接读入即可，但是借助跳板怎么实现呢，对于一条再长的路径，也可以看作是有限的直接相连的点的相连，这样可以得到一个状态转移方程，对于u、v和中继结点k，e[u][v] = min(e[u][v], e[u][k]+e[k][v])，因此遍历每一个结点成为中继结点即可

代码部分

    // cmp = (1<<30)
    // 没有直接相连的边的处理是memset(e, 127, sizeof 127);
    for(int k=1; k<=n; k++) {
        for(int u=1; u<=n; u++) {
            //这里做了两个小小的优化，可以优化部分情况
            if(e[u][k] < cmp) {
                for(int v=1; v<=n; v++) {
                    if(e[k][v] < cmp) {
                        e[u][v] = min(e[u][v], e[u][k]+e[k][v]);
                    }
                }
            }
        }
    }