C++实现---图

一、图的基本概念

1、图的定义

    图通常表示为 G = (V, E)。图(Graph)通常是由 顶点集合(Vertex) 和 顶点间的关系(Edge) 构成的一种数据结构。

    V 通常代表顶点集合。V = { x | x 属于某个非空数据对象集} 

    E 通常代表顶点间的关系的集合(也叫做边的集合)。E = {(x, y)| x 和 y 均属于V}

    通俗解释：V 表示全部的顶点，E 表示边的关系 ，(x, y) 表示边 x -> y。

2、有向图：

    有向图就是有方向区别的图。在有向图中，(x, y) 和 (y, x) 是不一样的，分别表示为 x -> y 和 y -> x 。

3、无向图

    无向图就是没有方向区别的图。在无向图中，(x, y) 和 (y, x) 是一样的，都表示为 x <--> y

    即：有向图 (x, y) 和 (y, x) 可以表示为无向图 (x, y)

4、完全图

    无向完全图：**任意两个顶点有且只有一条边**就称为无向完全图。

    即：若有 n 个顶点，无向完全图有 **n*(n-1) / 2**条边。

    有向完全图：**任意两个顶点有且只有两条方向相反的边**就称为无向完全图

    即：可以理解为无向完全图加上方向，因此，若有 n 个顶点，有向完全图有 **n*(n-1)** 条边

5、邻接顶点

    在无向图中，若 (u, v) 是一条边，则 u 和 v 互为邻接顶点。

    在有向图中，若 (u, v) 是一条边，则称 u 邻接到 v

    简记：若有一个顶点 u ，它能直接到 哪，它就邻接到哪。

6、顶点的度

    顶点的度指与它相关联的边的条数。

    在有向图中，顶点的度为出边和入边之和。

7、路径

    从一个顶点到另一个顶点的顶点序列。

8、路径长度

    带权路径长度：经过的每条边的权相加

    不带权路径长度：经过的边数(所有边权为1)

9、回路

    若一个顶点通过其他顶点能回来，就称为回路。      ![](https://i-blog.csdnimg.cn/direct/0e6eaaa15259416495b854c68d256492.png)

10、连通图

    图中任意一个顶点都是连通的，则称为连通图。

11、强连通图

    图中任意两个顶点 v 和 u ，存在 v 到 u 的路径，也存在 u 到 v 的路径，则称为强连通图。

    下图举的是有向图的例子

12、子图

    一个图的一部分，称为子图。

13、生成树

    一个图的最小连通子图，被称为生成树。

    生成树也就是形如：用 n-1 条边，将 n 个顶点连起来的图

二、图的存储结构

1、邻接矩阵

    ①、邻接矩阵是二维数组(假设为 vv )，它的行和列都是顶点，vv[i][j] 表示** i 下标的顶点**直接到 **j 下标的顶点**的权值(无权值则表示为1)，**无法直接到达的话，在有权值情况下为无穷，无权值则为0**。

     ②、**无向图的邻接矩阵是对称的**。因为在无向图中，A 能直接到 B，那么 B 也一定能直接到 A，表示为 vv[i][j] == vv[j][i]。

2、邻接表

    邻接表存的是边的结构体链表数组，数组每一个下标代表一个顶点，在该位置存的就是该顶点的边的链表。(类似哈希桶)

    有向图还会分出边表和入边表，就是分别存出边和入边。

3、总结

    稠密图用邻接矩阵更佳，因为稠密图邻接表太复杂。

    稀疏图用邻接表更佳，因为邻接矩阵浪费空间。

三、图的遍历

   ** 图的框架**

// V 为顶点类型，W 为权重，Direction 是否为有向图
    template<class V, class W, W W_MAX = INT_MAX, bool Direction = false>
    class Graph
    {
    public:
        
    private:
        std::vector<V> _vertexs; // 存放顶点的数组
        std::unordered_map<V, int> _vtoi; // 通过顶点确定_vertexs数组下标
        std::vector<std::vector<W>> _matrix; // 邻接矩阵
    };

     **一些成员函数**

// 构造函数
Graph() = default;
Graph(const V* vs, size_t n)
{
    _vertexs.resize(n);
    for (int i = 0; i < n; ++i)
    {
        _vertexs[i] = vs[i];
        _vtoi[vs[i]] = i;
    }

    _matrix.resize(n);
    for (int i = 0; i < n; ++i)
    {
        _matrix[i].resize(n, W_MAX);
    }
}

// 通过顶点找它在顶点数组中对应的下标
int GetVertexIndex(const V& v)
{
    auto iter = _vtoi.find(v);
    if (iter == _vtoi.end())
    {
        throw std::invalid_argument("顶点不存在");
        return -1;
    }
    else
        return iter->second;
}

// 通过起止顶点和权值添加边
void AddEdge(const V& src, const V& dst, const W& w)
{
    int srcIndex = GetVertexIndex(src);
    int dstIndex = GetVertexIndex(dst);

    _AddEdge(srcIndex, dstIndex, w);
}

// 写成子函数形式，怕 V 是int
// 根据起止顶点下标及权值添加边
void _AddEdge(int srcIndex, int dstIndex, const W& w)
{
    _matrix[srcIndex][dstIndex] = w;
    if (Direction == false)
        _matrix[dstIndex][srcIndex] = w;
}

1、深度优先遍历

    深度优先遍历就是从一个顶点开始，碰到下一个顶点就遍历过去，不断向下，用标志位数组记录遍历过的顶点，向没有碰到过的顶点遍历，如果该顶点所有邻接顶点都遍历过了，则返回上一层，再不断重复这个过程。

void _dfs(std::vector<bool>& flag, const V& v)
{
    // 顶点的个数
    size_t n = _vertexs.size();
    // 该顶点的下标
    int pos = GetVertexIndex(v);
    // 标记位置为 false 代表遍历过了
    flag[pos] = false;

    // 打印 观察
    std::cout << v << std::endl;

    // 遍历邻接矩阵这一行，找到能到达的顶点
    for (size_t i = 0; i < n; ++i)
    {
        // 能到达 并且 未遍历过
        if (_matrix[pos][i] != W_MAX && flag[i])
        {
            // 再进入
            _dfs(flag, _vertexs[i]);
        }
    }
}
void dfs(const V& v)
{
    size_t n = _vertexs.size();
    // true 代表未遍历到
    std::vector<bool> flag(n, true);
            
    _dfs(flag, v);
}

2、广度优先遍历

    广度优先遍历就是先从一个顶点开始，遍历它的全部邻接顶点，再从它的邻接顶点中，再遍历全部邻接顶点。

void bfs(const V& v)
{
    size_t n = _vertexs.size();
    int pos = GetVertexIndex(v);

    // true 代表未遍历到
    std::vector<bool> flag(n, true);

    std::queue<int> q;
    q.push(pos);
    flag[pos] = false;

    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        std::cout << _vertexs[front] << std::endl;
        for (size_t i = 0; i < n; ++i)
        {
            if (_matrix[front][i] != W_MAX && flag[i])
            {
                flag[i] = false;
                q.push(i);
            }
        }
    }

}

四、最小生成树

1、Kruskal 算法

    ①、前置知识：如果一个图有回路，那么它一定不是生成树，因为生成树是只有 n-1 条边的连通图(在有 n 个顶点的情况下)，如果有回路，那么要么边数不匹配，要么不连通。

    **②、算法原理：**不断选最小的边，并判断是否构成回路。如果未构成环路，就将边加入最小生成树，如果构成环路，就放弃这条边，继续去选下一条最小的边。不断循环至无边可找，或已经找到 n-1 条边。如果最后找出的边不足 n-1 条，那么说明没有最小生成树。

    ③、Kruskal 算法只能找出相对比较小的生成树，它找出来的生成树不一定是绝对最小的。

     ④、判环路：我这里判断是否成环用的是并查集，也可以用 unordered_set 等判断。

            只要把选过的边的两个顶点放进一个容器，然后在新的边要进入时判断，它的两个顶点是否都在这个容器内，如果都在的话，就会构成回路。

想了解并查集可以点击这里哦(o´ω`o)ﾉ

// 一些成员函数写在了三、图的遍历开头处
// 边的结构体
struct Edge
{
    int _srci;
    int _dsti;
    W _w;

    Edge(int srci = 0, int dsti = 0, W w = W())
        :_srci(srci)
        ,_dsti(dsti)
        ,_w(w)
    {}

    bool operator>(const Edge& e) const
    {
        return _w > e._w;
    }

};

typedef Graph<V, W, W_MAX, Direction> self;
// 输出型参数 minTree, 给外界返回最小生成树
// 返回该最小生成树总的权值
W Kruskal(self& minTree)
{
    // 初始化
    minTree._vertexs = _vertexs;
    minTree._vtoi = _vtoi;
    size_t n = _vertexs.size();
    minTree._matrix.resize(n);
    for (size_t i = 0; i < n; ++i)
    {
        minTree._matrix[i].resize(n, W_MAX);
    }

    // 将边录入优先级队列
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < n; ++j)
        {
            if (i < j && _matrix[i][j] != W_MAX)
                pq.push(Edge(i, j, _matrix[i][j]));
        }
    }

    // 不断找最小边，并将找到的边放入并查集
    int count = 0;
    W total_w = W();
    
    // 并查集，详情可以点上面链接看看哦，也可以用其他的来判断环路
    UnionFindSet ufs(n);
    while (!pq.empty())
    {
        // 取权值最小的边
        Edge minEdge = pq.top();
        pq.pop();
        
        // 判断是否在一个集合中，在一个集合返回的是 true
        if (!ufs.InSet(minEdge._srci, minEdge._dsti))
        {
            // 将起点和终点并入一个集合
            ufs.Union(minEdge._srci, minEdge._dsti);
            // 根据起始顶点，终点，权值 来添加边
            minTree._AddEdge(minEdge._srci, minEdge._dsti, minEdge._w);
            count++;
            total_w += minEdge._w;
            // 打印输出观察
            std::cout << _vertexs[minEdge._srci] << "-" << _vertexs[minEdge._dsti]
                << ": " << minEdge._w << std::endl;
        }
        // 如果已经选了 n-1 条边，那么就不需要再选了
        if (count == n - 1)
            break;
    }
    
    // 如果没选到 n-1 条边，就说明没有最小生成树
    if (count == n - 1)
    {
        return total_w;
    }
    else
    {
        // 不存在返回权值的默认构造值
        return W();
    }
}

 测试图：

2、 Prim 算法

    算法原理：与 Kruskal 算法不一样，Prim 算法是从一个顶点出发，选择与这个顶点关联的边中最小的边，并将与该边终点关联的边入队列，再从这些边中选择最小的边，不断重复这个选边，入边，再选的过程。

   ** 具体步骤：**

    1、先定义两个集合 X 和 Y，X 代表已经关联过的顶点，Y代表未关联过的顶点。

    2、从与 X 集合中的顶点相连的边中，选择一条最小的边，并判断其终点是否在集合 Y 中(判断环路)，若在集合Y，则将它的终点从 Y 中移除，加入 X 中，并将与它相连的边加入优先级队列中。若不在集合Y，则说明构成环路，重新选边。

    3、已经找到 n-1 条边就没必要继续找了，可以提前退出循环。如果最后找出的边不足 n-1 条，那么说明没有最小生成树。

// 一些成员函数写在了三、图的遍历开头处
// 边的结构体
struct Edge
{
    int _srci;
    int _dsti;
    W _w;

    Edge(int srci = 0, int dsti = 0, W w = W())
        :_srci(srci)
        ,_dsti(dsti)
        ,_w(w)
    {}

    bool operator>(const Edge& e) const
    {
        return _w > e._w;
    }

};

// 输出型参数 minTree, 给外界返回最小生成树
// start 开始顶点
// 返回值是总的权值
W Prim(self& minTree, const V& start)
{
    // 初始化 minTree
    size_t n = _vertexs.size();
    minTree._vertexs = _vertexs;
    minTree._vtoi = _vtoi;
    minTree._matrix.resize(n);
    for (size_t i = 0; i < n; ++i)
    {
        minTree._matrix[i].resize(n, W_MAX);
    }

    int starti = _vtoi[start];

    // 初始化 X 和 Y
    // true 代表该下标表示顶点在集合中
    std::vector<bool> X(n, false);
    std::vector<bool> Y(n, true);
    X[starti] = true;
    Y[starti] = false;
            
    // 将顶点start关联的边入优先级队列
    std::priority_queue <Edge, std::vector<Edge>, std::greater<Edge>> pq;
    for (size_t i = 0; i < n; ++i)
    {
        if (i != starti && _matrix[starti][i] != W_MAX)
        {
            pq.push(Edge(starti, i, _matrix[starti][i]));
        }
    }

    int count = 0;
    W total_w = W();

    while (!pq.empty())
    {
        Edge minEdge = pq.top();
        pq.pop();

        int srci = minEdge._srci;
        int dsti = minEdge._dsti;
        // 只能由集合 X -> Y
        if (Y[dsti])
        {
            minTree._AddEdge(srci, dsti, minEdge._w);
            count++;
            total_w += minEdge._w;
            // 从 Y 中移除，加入到 X 中
            Y[dsti] = false;
            X[dsti] = true;

            // 打印观察
            std::cout << _vertexs[minEdge._srci] << "-" << _vertexs[minEdge._dsti]
                << ": " << minEdge._w << std::endl;

            if (count == n - 1)
                break;

            for (size_t i = 0; i < n; ++i)
            {
                // 终点必须在集合 Y 中
                if (Y[i] && _matrix[dsti][i] != W_MAX)
                {
                    pq.push(Edge(dsti, i, _matrix[dsti][i]));
                }
            }
        }
    }

    if (count == n - 1)
    {
        return total_w;
    }
    else
    {
        return W();
    }
}

3、测试用例代码

void test_graph()
{
    const char* a = "abcdefghi";
    lw::Graph<char, int, INT_MAX, false> gh(a, strlen(a));
    gh.AddEdge('a', 'b', 4);
    gh.AddEdge('a', 'h', 8);
    gh.AddEdge('b', 'c', 8);
    gh.AddEdge('b', 'h', 11);
    gh.AddEdge('c', 'i', 2);
    gh.AddEdge('c', 'd', 7);
    gh.AddEdge('c', 'f', 4);
    gh.AddEdge('d', 'e', 9);
    gh.AddEdge('d', 'f', 14);
    gh.AddEdge('e', 'f', 10);
    gh.AddEdge('f', 'g', 2);
    gh.AddEdge('g', 'h', 1);
    gh.AddEdge('g', 'i', 6);
    gh.AddEdge('h', 'i', 7);
    lw::Graph<char, int> minTree;

    // std::cout << "总的权值: " << gh.Kruskal(minTree) << std::endl;
    std::cout << "总的权值: " << gh.Prim(minTree, 'a') << std::endl;
}

五、单源最短路径

1、Dijkstra算法

    ①、算法前提：Dijkstra 算法是单源最短路径算法，所有边的权值都应该大于 0。

                      该算法是求一个顶点到其他顶点的最短路径。

    ②、算法原理：

    1、**定义两个数组 dict **(存源顶点到下标表示顶点的距离), **pPath** (表示在最短路径上该顶点的父节点的下标)。

    2、**初始化两个数组**，假设源节点在 0 号位置，**dict 初始化{0, ∞, ∞, ∞ ,....}**，因为自己到自己的距离为0。**pPath 初始化为{-1, -1, -1, -1, .....}**，-1 表示没有父节点 。

    3、从 源顶点 出发，**找最近的顶点 x (也就是 min{dict})**，如果从 x 出发到达的路径比从 dict 上记录的路径**短**(假设到 i 节点，也就是：dict[x] + _matrix[x][i] < dict[i])，那么就**更新 dict 数组**为 dict[x] + _matrix[x][i]和 **pPath 数组** pPath[i] = x的下标。

    4、**不断重复 3 过程**，在无负权值的情况下，找过的顶点已经可以确认是最短路径了，所以可以**记录找过的顶点，将所有顶点都遍历一遍**，就完成了该算法。

    **补充：为什么不断选min{dict}遍历过的顶点一定是最短路径呢？**

    答：首先第 1 次选出的顶点一定是最短路径，因为到其他顶点都比到它远，因此，不可能存在路径，从源顶点出发，通过其他顶点，距离 小于 直接从源顶点到该顶点的距离。由此，我们可以类推出第 2 次、第 3 次 和之后选的顶点一定是最短距离。

// 一些成员函数写在了三、图的遍历开头处

// pPath 存该顶点的父路径 dict 存该顶点到其他顶点的最短距离
void Dijkstra(const V& v, std::vector<int>& pPath, std::vector<int>& dict)
{
    // 获得顶点个数 与 源顶点下标
    size_t n = _vertexs.size();
    int srci = GetVertexIndex(v);

    // 初始化两个数组
    pPath.resize(n, -1);
    dict.resize(n, W_MAX);
    dict[srci] = 0;

    // 定义数组，记录已经走过的顶点
    std::vector<int> flag(n, false);
            
    while (true)
    {
        // 找到距离最近的顶点
        int minVal = W_MAX;
        int mini = -1;
        for (size_t i = 0; i < n; ++i)
        {
            if (flag[i] == false && minVal > dict[i])
            {
                mini = i;
                minVal = dict[i];
            }
        }
        // 遍历完所有顶点，退出
        if (mini == -1) break;
        // 走过的顶点，标记为 true
        flag[mini] = true;

        // 找是否有更短的路径
        for (size_t i = 0; i < n; ++i)
        {
            // 判断 s->i 是否比 s->mini + mini->i 更短
            // !flag[i] 表示只能从未走过的顶点中找，因为走过的已经是最短路径了
            // _matrix[mini][i] != W_MAX 表示找能到达的路径
            if (!flag[i] && _matrix[mini][i] != W_MAX
                && dict[mini] + _matrix[mini][i] < dict[i])
            {
                dict[i] = dict[mini] + _matrix[mini][i];
                pPath[i] = mini;
            }
        }
    }
}

     **通过 pPath 数组找到最短路径的具体路径**

void PrintPath(const vector<int>& pPath, const vector<int>& dict)
{
    size_t n = _vertexs.size();
    for (size_t i = 0; i < n; ++i)
    {
        // 找路径
        std::vector<int> path;
        int parent = pPath[i];
        while (parent >= 0)
        {
            path.push_back(parent);
            parent = pPath[parent];
        }
        
        // 因为是从下往上找父亲，所以 path 存的是倒着的父节点列表 
        std::reverse(path.begin(), path.end());
        
        // 先打印该顶点的下标
        std::cout << "[" << i << "]: ";
        for (int vi : path)
        {
            // 不断打印父节点
            std::cout << _vertexs[vi] << " -> ";
        }
        // 最后打印 自己 和 距离
        std::cout << _vertexs[i] << " / " << dict[i] << std::endl;
    }
}

    **测试用例**

void test3_graph()
{
    const char* a = "syztx";
    lw::Graph<char, int, INT_MAX, true> gh(a, strlen(a));
    gh.AddEdge('s', 't', 10);
    gh.AddEdge('s', 'y', 5);
    gh.AddEdge('y', 't', 3);
    gh.AddEdge('y', 'x', 9);
    gh.AddEdge('y', 'z', 2);
    gh.AddEdge('z', 's', 7);
    gh.AddEdge('z', 'x', 6);
    gh.AddEdge('t', 'y', 2);
    gh.AddEdge('t', 'x', 1);
    gh.AddEdge('x', 'z', 4);
    vector<int> dict;
    vector<int> pPath;
    gh.Dijkstra('s', pPath, dict);
    gh.PrintPath(pPath, dict);

    int x = 0;
}

2、BellmanFord算法

    算法简介：上述的 Dijkstra 算法无法解决带负权的问题，因为当遇到负权时，每次选最短边的贪心算法会失效。而 BellmanFord 算法可以解决带负路径的算法，它是一种偏暴力的算法。但BellmanFord算法无法解决带负权回路问题。

    算法原理：

     1、和 Dijkstra 算法一样，**定义两个数组 dict **(存源顶点到下标表示顶点的距离), **pPath** (表示在最短路径上该顶点的父节点的下标)。

    2、**初始化两个数组**，假设源节点在 0 号位置，**dict 初始化{0, ∞, ∞, ∞ ,....}**，因为自己到自己的距离为0。**pPath 初始化为{-1, -1, -1, -1, .....}**，-1 表示没有父节点 。

    3、**松弛操作**：以每个顶点为中间节点(i) ，判断源顶点到与 i 相连的顶点(j) 是否有更小的值。也就是判断 dict[i] + i->j 和 dict[j] 的大小。

    4、将松弛操作**循环 n 次**，就完成了找最短路径的问题。

    补充：

    1、为什么进行 n 次松弛操作 (其实只要 n-1 次，n 次是为了判断负权回路) 就一定能够找出最短路径呢？

    答：因为一次松弛操作，至少可以找出最短的一条边，而图中的最短路径，最多就是把所有顶点都连起来，也就是 n-1 条边，因此，循环 n-1 次就一定可以找出最短路径。

    如果第 n 次还在更新，我们就可以判断它有负权回路。

     2、为什么该算法无法解决负权回路的问题？

    答：因为如果带负权回路的话，它会一直转圈更新，永远找不到最短路径。

** 代码如下： **

// 一些成员函数写在了三、图的遍历开头处

bool BellmanFord(const V& v, vector<int>& pPath, vector<int>& dict)
{
    // 拿到 源顶点的下标
    size_t srci = GetVertexIndex(v);
    // 顶点个数
    size_t n = _vertexs.size();

    // 初始化两个数组
    pPath.resize(n, -1);
    dict.resize(n, W_MAX);
    dict[srci] = 0;

    // 循环 n 次
    for (size_t k = 0; k < n; ++k)
    {
        // 一次松弛操作最坏能将最短一条边找到
        bool flag = false; // 是否更新，false为未更新
        // 打印调试信息
        printf("第%d轮: \n", k + 1);
        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = 0; j < n; ++j)
            {
                // 判断 s->i + i->j < s->j
                // 我们要先保证 i 可到达：dict[i] != W_MAX
                // i 可以到 j：_matrix[i][j] != W_MAX 
                if (dict[i] != W_MAX && _matrix[i][j] != W_MAX 
                    && dict[i] + _matrix[i][j] < dict[j])
                {
                    // 更新最多路径及父节点
                    dict[j] = dict[i] + _matrix[i][j];
                    pPath[j] = i;

                    // 标记为以更新
                    flag = true;
                    // 打印调试信息
                    printf("更新: %c->%c: %d\n", _vertexs[i], _vertexs[j], dict[j]);
                }
            }
        }
        // 如果第 n 次还有更新，说明构成负权回路
        if (k == n - 1 && flag)
        {
            std::cout << "构成负权回路\n";
            return false;
        }
        // 没更新了就说明都更新完了
        if (!flag)
        {
            break;
        }
    }
    return true;
}

   ** 打印路径的函数： **

void PrintPath(const vector<int>& pPath, const vector<int>& dict)
{
    size_t n = _vertexs.size();
    for (size_t i = 0; i < n; ++i)
    {
        // 找路径
        std::vector<int> path;
        int parent = pPath[i];
        while (parent >= 0)
        {
            path.push_back(parent);
            parent = pPath[parent];
        }
        
        // 因为是从下往上找父亲，所以 path 存的是倒着的父节点列表 
        std::reverse(path.begin(), path.end());
        
        // 先打印该顶点的下标
        std::cout << "[" << i << "]: ";
        for (int vi : path)
        {
            // 不断打印父节点
            std::cout << _vertexs[vi] << " -> ";
        }
        // 最后打印 自己 和 距离
        std::cout << _vertexs[i] << " / " << dict[i] << std::endl;
    }
}

    **测试用例： **

// 最坏情况测试
void test5_graph()
{
    const char* a = "EDCBA";
    lw::Graph<char, int, INT_MAX, true> gh(a, strlen(a));
    gh.AddEdge('A', 'B', 1);
    gh.AddEdge('B', 'C', 2);
    gh.AddEdge('C', 'D', 3);
    gh.AddEdge('D', 'E', 4);
    // gh.AddEdge('C', 'B', -5);
    
    vector<int> dict;
    vector<int> pPath;
    if (gh.BellmanFord('A', pPath, dict))
        gh.PrintPath(pPath, dict);
    else
        cout << "带负权回路" << endl;
}

    最坏情况的运行结果：

六、多源最短路径算法

FloydWarshall算法

    算法简介：多源指的是将上述单源最短路径得到的距离表和父路径表扩到二维，能够得到每个顶点到其他顶点的最小距离和路径。

    算法原理：FloydWarchall 算法采用了动态规划的算法，顶点 i 到顶点 j 有两种可能，一种是经过一系列顶点 k 到达 j，另一种是直接从 i 到 j，我们只要遍历所有顶点，查找 i -> {k} -> j 的最小值，并更新两个二维表 即可。

    补充：两个二维表是单源最短路径算法中的 dict 和 pPath 扩到二维，dict 中 i->j 表示 i->j 的最短距离，pPath 中的 i->j 表示 i->j 路径上 j 的父节点。

   ** 代码：**

void FloydWarshall(vector<vector<int>>& dict, vector<vector<int>>& pPath)
{
    // 顶点个数
    int n = _vertexs.size();

    // 初始化两个二维数组
    dict.resize(n);
    pPath.resize(n);
    for (size_t i = 0; i < n; ++i)
    {
        dict[i].resize(n, W_MAX);
        pPath[i].resize(n, -1);
    }

    // 将原本的信息填入两个二维表内
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < n; ++j)
        {
            // 自己到自己距离为0, 负节点为默认的 -1
            if (i == j)
            {
                dict[i][j] = 0;
            }
            else if (_matrix[i][j] != W_MAX) 
            {
                // 将图的内容填入dict表并更新父节点
                dict[i][j] = _matrix[i][j];
                pPath[i][j] = i;
            }
        }
    }

    for (size_t k = 0; k < n; ++k)
    {
        // 用每个点作为中间点 k 更新
        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = 0; j < n; ++j)
            {
                // i->k + k->j < i->j
                // 判断当前记录的 i 直接到 j 与经过 k 到 j 哪个更短
                if (dict[i][k] != W_MAX && dict[k][j] != W_MAX
                    && dict[i][k] + dict[k][j] < dict[i][j])
                {
                    dict[i][j] = dict[i][k] + dict[k][j];
                    // 更新后 i->j 的父节点不是 k !!!
                    // 因为 k->j 的父节点不一定是 k，也有可能是被更新过的
                    pPath[i][j] = pPath[k][j];
                }
            }
        }
    }
}

    **测试代码： **

void test6_graph()
{
    const char* a = "ABCDE";
    lw::Graph<char, int, INT_MAX, true> gh(a, strlen(a));
    gh.AddEdge('A', 'B', 1);
    gh.AddEdge('B', 'C', 2);
    gh.AddEdge('C', 'D', 3);
    gh.AddEdge('D', 'E', 4);

    vector<vector<int>> dict;
    vector<vector<int>> pPath;
    gh.FloydWarshall(dict, pPath);

    std::cout << "路径表:\n";
    for (size_t i = 0; i < dict.size(); ++i)
    {
        for (size_t j = 0; j < dict[i].size(); ++j)
        {
            if (dict[i][j] == INT_MAX)
                std::cout << "#\t";
            else
                std::cout << dict[i][j] << "\t";
        }
        std::cout << std::endl;
    }
    std::cout << "父路径表:\n";
    for (size_t i = 0; i < dict.size(); ++i)
    {
        for (size_t j = 0; j < dict[i].size(); ++j)
        {
            std::cout << pPath[i][j] << "\t";
        }
        std::cout << std::endl;
    }
    // 也可以将 pPath[i] 和 dict[i] 传到我们上面写的 PrintPath 打印调试
}

    感谢大家观看♪(･ω･)ﾉ