Floyd

Floyd 算法（也称为 Floyd-Warshall 算法）是一种用于计算加权图中所有顶点对之间最短路径的算法。它是一种动态规划算法，能够处理负权边，但不能处理负权环。Floyd 算法的主要优点是能够同时计算所有顶点对之间的最短路径，而不仅仅是单源最短路径。

算法原理

Floyd 算法的基本思想是通过动态规划的方式，逐步更新所有顶点对之间的最短路径。算法利用一个三重循环来检查每一对顶点之间的路径，尝试通过其他顶点来更新它们之间的最短路径。

算法步骤

1. 初始化:

   • 创建一个二维数组 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短距离。
   • 如果 i 和 j 之间有边，则 dist[i][j] 初始化为边的权重；如果没有边且 i 不等于 j，则初始化为正无穷（表示不可达）；如果 i == j，则初始化为 0（表示到自身的距离）。

2. 动态规划更新:

   • 使用三重循环，遍历每个顶点 k 作为中间点，对每一对顶点 (i, j) 进行更新：

     if dist[i][j] > dist[i][k] + dist[k][j]:
      dist[i][j] = dist[i][k] + dist[k][j]

   • 这表示如果通过顶点 k 到达 j 的路径比直接从 i 到 j 的路径更短，则更新 dist[i][j]。

3. 结果输出:

   • 最终，dist[i][j] 数组中的值即为从顶点 i 到顶点 j 的最短路径长度。

时间复杂度

• Floyd 算法的时间复杂度为 (O(V^3))，其中 (V) 是图中顶点的数量。这是因为算法需要三重循环遍历所有顶点对和中间点。

代码实现

以下是 Floyd 算法的 C++ 实现：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // 定义无穷大

void floydWarshall(int V, vector<vector<int>>& graph) {
    // 初始化距离矩阵
    vector<vector<int>> dist(V, vector<int>(V, INF));

    // 将边的权重填入距离矩阵
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (i == j) {
                dist[i][j] = 0; // 自身到自身的距离为0
            } else if (graph[i][j] != INF) {
                dist[i][j] = graph[i][j]; // 有边时初始化为边的权重
            }
        }
    }

    // 动态规划更新距离矩阵
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短路径
                }
            }
        }
    }

    // 打印结果
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

    // 使用邻接矩阵表示图，初始化为无穷大
    vector<vector<int>> graph(V, vector<int>(V, INF));

    // 初始化对角线为0
    for (int i = 0; i < V; ++i) {
        graph[i][i] = 0;
    }

    cout << "Enter edges (u, v, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u][v] = weight; // 添加边
    }

    floydWarshall(V, graph);

    return 0;
}

代码解析

1. 数据结构:

   • 使用一个二维数组 graph 来表示图的邻接矩阵，初始值为无穷大（INF）。
   • 对角线元素（自身到自身的距离）初始化为 0。

2. 初始化:

   • 将所有边的权重填入 dist 矩阵，初始化为边的权重或无穷大。

3. 动态规划更新:

   • 三重循环遍历所有顶点，更新最短路径。

4. 输出结果:

   • 打印最终的最短路径矩阵。

优势与劣势

优势:

• Floyd 算法能够同时计算所有顶点对之间的最短路径，适合于密集图。
• 算法简单，易于实现。

劣势:

• 时间复杂度较高，适用于顶点数量较小的图（一般 (V \leq 100)）。
• 不适用于具有负权环的图。

Floyd 算法是一种强大的算法，适用于计算加权图中所有顶点对之间的最短路径。通过动态规划的方法，它能够高效地更新路径长度，尽管在处理大规模图时可能受到时间复杂度的限制。Floyd 算法在许多应用场景中都非常有用，如网络路由、交通流量分析等。