基础介绍

Floyd算法，中文名称弗洛伊德算法，这是一个图算法，用于求解图中每对顶点之间的最短路径问题。这是一个经典的动态规划算法，用来解决图中任意两个顶点对间最小路径的问题。

算法原理

我们知道动态规划算法的本质是将问题分解为子问题，遵从由底向上的解题思路。动态规划算法一般采用的多重循环的方式来实现，每一个问题的背后都与前一个子问题相关。那弗洛伊德算法的原理是什么呢？

假设一个图中有n个顶点，这个图采用邻接矩阵的方式来实现。弗洛伊德算法也是基于邻接矩阵的方式实现。对于任意两点i和j之间的最短路径，如果存在一个中间点k，使得从i经过k到j的路径比直接从i到j的路径更短，则更新i到j的最短距离。

从一本数据结构书籍上也有下面的论述：

假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为arcs[i]​[j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（vi, v0, vj）是否存在（判别弧（vi, v0）和（v0, vj）是否存在）​。如果存在，则比较（vi, vj）和（vi, v0, vj）的路径长度，取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果（vi, …, v1）和（v1, …,vj）分别是当前找到的中间顶点的序号不大于0的最短路径，那么（vi, …, v1, … , vj）就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探，依此类推。在一般情况下，若（vi, …, vk）和（vk, …, vj）分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi, …, vk, …, vj）和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。

 这句话应该如何理解呢？如何分解子问题呢？下面先把弗洛伊德算法的核心算法贴出来，结合核心算法来理解这个问题：

void floyd(vector<vector<int>>& dist, int n) {
    // dist[i][j] 表示从i到j的最短距离
    
    // k是中间节点
    for(int k = 0; k < n; k++) {
        // i是起点
        for(int i = 0; i < n; i++) {
            // j是终点
            for(int j = 0; j < n; j++) {
                // 如果经过k点的路径比原来的路径短，则更新
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && 
                   dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

图的顶点每个都有序号，序号的范围从0-n-1（因为有n个顶点），假设中间顶点的序号为k，起始顶点的序号分别为i和j，（vi, …, vk, … , vj）的含义是vk顶点为一个vi和vj之间的一个顶点，这个中间的含义并不是指它在vi到vj路径的正中间，而是说只要vk在vi和vj的路径上都算在中间了，请看下面的例子：

假设i=3，j=6，n=10，k=5，这个组合的意思是一个图包含10个顶点，现在从顶点3到顶点6经过不大于顶点5的路径，那有哪些组合呢？下面的组合都是可以与（vi, …, vk, … , vj）对应：

（v3,v5, v1,v4, v6）

（v3,v0, v5,v2, v3,v4,v6）

（v3,v3,v4,v0, v1,v5,v6）

（v3,v5,v6）

.......

上面的组合都是正确的，即在这个路径上只要包含v5就可以，这个路径上出现的顶点序号不能超过5，换句话说就是求解v3到v6路径上包含不大于v5顶点的最小值。到这里相信大家应该理解了中间顶点的含义了。

假设D[i][j]表示vi到vj之间的最短距离，初始化为两个顶点的直接相连的值。这个动态规划算法的状态转移方程：

现在有了状态转移方程，那么从开始进行推导：

D[i][j]初始化为vi和vj直连的权重值。

当k=0时，即要求vi到vj之间必须经过顶点v0，那么根据转移方程，求解D[i][j]与D[i][0]+D[0][j]的较小值并更新，当k=0的值遍历所有顶点后，到该步骤结束，邻接矩阵中D[i][j]的值就是D[i][j]与D[i][0]+D[0][j]的较小值，即在这个步骤完成了所有顶点对之间最小路径直连或经过v0顶点二者之间的较小值，D[i][j]此时已经是表示在允许仅经过v0顶点的情况下所有路径的最小值，它代表的意义已经发生了变化。

当k=1时，即要求vi到vj之间的允许经过的顶点不大于v1(即vi到vj的路上仅允许包含v0和v1)，那么根据状态转移方程需要比较D[i][j]与D[i][1]+D[1][j]的大小并求较小值，这时候重点来了，D[i][j]的含义是上一个步骤求解出的值，即不包含v1顶点情况下的两个顶点间最小路径，现在D[i][1]表示的是vi和v1之间仅包含v0时最短路径，D[1][j]表示的是v1顶点到vj顶点仅包含不大于v0顶点的最小路径，这两个值在上k=0步骤已经计算出来并更新到了D[i][1]和D[1][j]，通过比较D[i][j]与D[i][1]+D[1][j]的较小值，得到了在包含v[1]顶点最小距离，这时候D[i][j]值的含义变成了在路径中包含了不大于顶点序号为1的最短路径。

以此类推，当k=k时，即表示vi到vj之间的允许经过的顶点不大于(即vi到vj的路上仅允许包含不大于顶点序号为k的顶点)，根据状态转移方程，要求解D[i][j]与D[i][k]+D[k][j]这二者的较小值，根据上面的推导，此时D[i][k]表示的是vi和vk之间包含不大于顶点序号为k-1时的最短路径，D[k][j]表示的是vk顶点到vj顶点包含不大于顶点序号为k-1的最小路径，这两个值在上k=k-1步骤已经计算出来并更新到了D[i][k]和D[1][k]，通过比较D[i][j]与D[i][k]+D[k][j]的较小值，得到了在包含v[k]顶点最小距离，这时候D[i][j]值的含义变成了在路径中包含了不大于顶点序号为k的最短路径。

直到k=n-1步骤结束时，D[i][j]表示的是在顶点vi和顶点vj之间，包含所有顶点的情况下的最短路径，这样也就实现了算法的目的。

通过上面算法的详细拆解，可以看到每当k增加时，就会在所有顶点对的路径上加上新增的顶点，通过上一层的计算结果，求本层的最短路径，层层递进，直到包含所有的顶点为止。

算法实现实例

class FloydSolver {
private:
    vector<vector<int>> dist;    // 距离矩阵
    vector<vector<int>> next;    // 路径矩阵
    int n;                       // 顶点数量
    
public:
    FloydSolver(int vertices) : n(vertices) {
        // 初始化距离矩阵和路径矩阵
        dist = vector<vector<int>>(n, vector<int>(n, INT_MAX));
        next = vector<vector<int>>(n, vector<int>(n, -1));
        
        // 初始化对角线
        for(int i = 0; i < n; i++) {
            dist[i][i] = 0;
            next[i][i] = i;
        }
    }
    
    // 添加边
    void addEdge(int from, int to, int weight) {
        dist[from][to] = weight;
        next[from][to] = to;
    }
    
    // Floyd算法主体
    void computeShortestPaths() {
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                        int newDist = dist[i][k] + dist[k][j];
                        if(newDist < dist[i][j]) {
                            dist[i][j] = newDist;
                            next[i][j] = next[i][k];  // 更新路径
                        }
                    }
                }
            }
        }
    }
    
    // 获取从start到end的最短路径
    vector<int> getPath(int start, int end) {
        if(dist[start][end] == INT_MAX) return {};
        
        vector<int> path;
        path.push_back(start);
        
        while(start != end) {
            start = next[start][end];
            path.push_back(start);
        }
        
        return path;
    }
    
    // 获取两点间的最短距离
    int getDistance(int start, int end) {
        return dist[start][end];
    }
};