$\Huge\color{orchid}{点击此处获取更多干货}$

Floyd算法

有向图中任意两节点$(s,e)$之间的最短距离，无非就从两种情况中产生：
1. 通过有向边$\left \{ s,e \right \}$由$s$直达$e$
2. 由$s$出发，经过若干有向边和中转节点，最终到达$e$

仿照Bellman-Ford算法部分，得到以下图表：

解释一下转移关系：
对于每个节点$k$，最短路径可以经过$k$，也可以不经过$k$。此时节点$k$视作未候选，候选中转节点就是$1 \sim k-1$，对应$d(k-1,i,j)$的状态，此时一种情况是从$i$出发，先走到$k$再走到$j$，就是$d(k-1,i,k) + d(k-1,k,j)$，另一种情况直接从$i$走到$j$，就是$d(k-1,i,j)$，两者取最小值。
由于对任意$k_0$，$k=k_0$状态仅与$k=k_0-1$状态有关，且两状态之间不会互相覆盖，故可以直接在原地修改

C++ 代码

对前置知识中MGraph类稍作修改

class MGraph {
private:
    int** mat;
    int numVex, numArc;
    const int INF = 1e9 + 7;//添加无穷大量

public:
    //构造函数稍作修改，预处理距离表
    MGraph(int n, int m) {
        numVex = n;
        numArc = m;
        mat = new int[numVex + 1];
        for (int i = 0; i <= numVex; i++) {
            mat[i] = new int[numVex + 1];
            //把邻接矩阵mat直接当作距离表
            fill(mat[i], mat[i] + numVex, INF);
            mat[i][i] = 0;
        }
        size_t s, e;
        int v;
        while (m--) {
            cin >> s >> e >> v;
            //不保证不存在重边和自环
            mat[s][e] = min(mat[s][e], v);
        }

        //按顺序枚举状态位k,i,j
        for (int k = 1; k <= numVex; k++) {
            for (int i = 1; i <= numVex; i++) {
                for (int j = 1; j <= numVex; j++) {
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
                }
            }
        }
    }

    //查询从s到e的最短距离
    int getShortestPath(int s, int e) {
        int& dist = mat[s][e];
        //Floyd算法也可以处理负权边，同样不支持负权回路
        return ((dist >= INF / 2) ? INT_MIN : dist);
    }

    //析构函数保持不变，此处暂时省略
}