C/C++环境下的弗洛伊德算法实现详解

C/C++环境下弗洛伊德算法实现深度剖析

弗洛伊德算法（Floyd's algorithm），也被称作弗洛伊德-沃尔什算法（Floyd-Warshall algorithm），是一种用于在加权图中探寻所有顶点对之间最短路径的算法。该算法适用于有向图与无向图，能够处理负权重边，但无法应对负权重循环。

弗洛伊德算法（Floyd-Warshall Algorithm）属于一种用于计算图中所有顶点对之间最短路径的动态规划算法。本文将会细致地讲解弗洛伊德算法的原理，并提供一个C++实现的示例，以此助力读者领会算法的运作原理以及编程技巧。

算法原理

弗洛伊德算法的核心思路是通过逐步探寻并更新所有顶点对之间的最短路径来解决问题。算法借助一个距离矩阵来存储顶点之间的距离，并且在每一步骤中会考虑通过一个新的中间顶点来更新这些距离。和之前介绍的Dijkstra算法原理类似，都是借助中转点来更新最短距离。不过，弗洛伊德算法处理的是多源的最短路问题。

算法步骤

1. 初始化一个距离矩阵，其中dist[i][j]代表顶点i到顶点j的直接距离。若i和j没有直接相连，那么dist[i][j]设为无穷大。
2. 对于每一个顶点k作为中间顶点，将dist[i][j]更新为min(dist[i][j], dist[i][k] + dist[k][j])。

弗洛伊德是典型的三重for循环，所以其时间复杂度为O(n^3)，这里的n是图中顶点的数量。第一层循环遍历中转点，第二层循环遍历起点，第三层循环遍历终点，对于图中点数量较多的情况，弗洛伊德算法的时间复杂度相对较高。

图解算法：

接下来我们以一个包含4个点的图来进行讲解，图中的边是有向边和无向边的结合。以邻接矩阵的方式进行存储，要是大家偏好用邻接表存储，也可以采用邻接表。下面介绍两个矩阵，矩阵A表示（i，j）i到j的最短距离，初始化为无穷大。矩阵B表示i到j路径中除去起点的第一个中转点，初始化为-1。

初始状态：

依据图中的点之间的距离进行赋值，矩阵A中i到i的距离都为0，无穷大表示无法到达。矩阵B初始化为-1。

第一步：

选取一个点（按顺序选取）作为中转点，查看以它作为中转点时，能否使所到达的点产生更小的距离，如果产生了，就更新矩阵A的距离以及矩阵B的中转点。我们先选取1号点，那么位于1号点的行和列的值不会发生变化，自身到自身的点距离永远是0，图中黄色标记的是此步不会改变的点，其他点可能会变化。在更新距离时无需看图也能更新矩阵，例如图中2号点到3号点原本距离为10，以1号点作为中转点，路径为2 - 1 - 3，此时距离为2 + 6 = 8 < 10，通过1号点绕路的方式距离更短。类似地，3到2号点、3到4号点、4到3号点等也会有相应更新。同时更新矩阵B。

更新后（红色标记为变化的值）：

第二步：

把2号结点当作中转结点，查看能够更新哪些最短路径，和上一步一样直接看图更新。比如4到1号点，距离为2 + 4 = 6 < 10；1到4号点，距离为2 + 4 = 6 < 10；3到4号点，距离为8 + 4 = 12 < 16等。对于一些无法更新的值，例如1到3号点，2 + 8 = 10 > 6，就不进行更新。

对于矩阵B，要注意3到4和4到3的路径相反，更新时3到4号点的第一个中转点还是1号点。更新后（红色标记为变化的值）：

第三步：

把3号点作为中转结点，像前几步一样继续寻找最短距离。经过更新发现3号点作为中转点无法更新任何距离，所以矩阵A、B不需要更新。在图中验证可知3号点中转距离反而变大，因此不更新。

第四步：

把4号点作为中转点，继续更新最短距离。发现和3号点一样，无法更新任何距离，在矩阵A中除了黄色的点之外，所能连起来的矩形中，主对角线顶点值相加都比当前值大。在图中也能验证，所以不进行更新。

这样就完成了所有点的更新，把所有点都当作中转点更新一遍，就完成了弗洛伊德算法，更新时每次按顺序把点当作中转点，遍历寻找路径的起点，再遍历寻找终点，算法时间复杂度为O(n^3)。

算法实现：

以下是弗洛伊德算法的C++实现示例：

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

// 定义图的顶点数
const int N = 100;
// 定义无穷大的初始距离
const int INF = numeric_limits<int>::max();

// 弗洛伊德算法的实现
void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    // 遍历所有顶点作为中间顶点
    for (int k = 0; k < n; k++) {
        // 遍历所有顶点作为起点
        for (int i = 0; i < n; i++) {
            // 遍历所有顶点作为终点
            for (int j = 0; j < n; j++) {
                // 如果通过顶点k可以找到更短的路径，则更新dist[i][j]
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n; // 顶点的数量
    cin >> n;

    vector<vector<int>> dist(n, vector<int>(n, INF)); // 初始化距离矩阵

    // 读取邻接矩阵
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0; // 自己到自己的距离是0
        for (int j = i; j < n; j++) {
            int w;
            cin >> w;
            dist[i][j] = w;
            dist[j][i] = w; // 如果是无向图，需要设置对称的权重
        }
    }

    // 执行弗洛伊德算法
    floydWarshall(dist);

    // 打印所有顶点对之间的最短路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << " ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

Floyd与Dijkstra算法比较

迪杰斯特拉算法（Dijkstra's algorithm）和弗洛伊德算法（Floyd-Warshall algorithm）都是图论中用于计算图中最短路径的知名算法。它们在某些方面有相似之处，但在设计和应用上存在明显差异，下面我们对这两种算法的相同点和不同点进行阐述。

相同点：

1. 目的：两者都致力于解决最短路径问题。
2. 适用性：它们都能够用于加权图中的最短路径计算，其中只有弗洛伊德算法可以处理负权边。

不同点：

1. 问题范围：

2. 迪杰斯特拉算法：主要用于单元路径的最短路问题，也就是从单一源点到所有其他顶点的最短路径。

3. 弗洛伊德算法：解决的是所有顶点对之间的最短路径问题，即计算图中每一对顶点之间的最短路径。

4. 时间复杂度：

5. 迪杰斯特拉算法：具有较高的效率，时间复杂度为O(V^2)（使用朴素实现）或O((V+E) log V)（使用优先队列优化）。（V为顶点数，E为边数）

6. 弗洛伊德算法：时间复杂度为O(V^3)，因为它需要计算所有顶点对的最短路径。

7. 实现方式：

8. 迪杰斯特拉算法：通常采用贪心策略，从一个顶点出发，逐步扩展到邻接顶点，直至找到所有顶点的最短路径。

9. 弗洛伊德算法：运用动态规划，通过三层循环迭代地改进路径长度，直到达到最优解。

10. 对负权边的处理：

11. 迪杰斯特拉算法：无法处理负权边，因为负权边会破坏算法的贪心选择性质。

12. 弗洛伊德算法：可以处理负权边，但图中不能存在负权环，否则最短路径问题无解。

13. 初始化：

14. 迪杰斯特拉算法：从源点到其他所有顶点的距离初始化为无穷大，源点到自身的距离为0。

15. 弗洛伊德算法：所有顶点到自身的距离初始化为0，其他顶点间的距离初始化为边的权重或无穷大（如果无直接连接）。

本篇对弗洛伊德算法进行了详细剖析，如果想要了解迪杰斯特拉算法，可以查看博主的上一篇博客，其中有针对迪杰斯特拉算法的详细讲解：迪杰斯特拉(Dijkstra)算法（C/C++)-CSDN博客

至此，全文即将结束，感谢大家的支持。