Floyd算法详解（C语言实现多源最短路径问题）

算法原理

假设我们有一个图，包含 n 个顶点。Floyd算法使用一个二维数组 dist[i][j] 来存储从顶点 i 到顶点 j 的最短距离。

算法的核心公式如下：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

其中，k 是当前考虑的中间节点。算法会依次尝试所有可能的中间节点 k（从0到n-1），并更新所有点对之间的最短路径。

C语言实现步骤

1. 初始化距离矩阵：如果两点直接相连，则填入边的权重；否则设为无穷大（通常用一个大数如INT_MAX/2表示）；自己到自己的距离为0。
2. 三重循环：外层循环遍历中间节点 k，内层两重循环遍历所有点对 (i, j)。
3. 根据核心公式更新 dist[i][j]。
4. 输出最终的距离矩阵，即任意两点间的最短路径。

完整C语言代码示例

#include <stdio.h>#include <limits.h>#define V 4  // 顶点数量#define INF 99999  // 表示无穷大// 打印距离矩阵void printSolution(int dist[][V]) {    printf("最短路径矩阵:\n");    for (int i = 0; i < V; i++) {        for (int j = 0; j < V; j++) {            if (dist[i][j] == INF)                printf("%7s", "INF");            else                printf("%7d", dist[i][j]);        }        printf("\n");    }}// Floyd-Warshall 算法实现void floydWarshall(int graph[][V]) {    int dist[V][V];    // 初始化距离矩阵    for (int i = 0; i < V; i++)        for (int j = 0; j < V; j++)            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][k] + dist[k][j] < dist[i][j]) {                    dist[i][j] = dist[i][k] + dist[k][j];                }            }        }    }    printSolution(dist);}int main() {    // 示例图的邻接矩阵    int graph[V][V] = {        {0,   3,   INF, 7},        {8,   0,   2,   INF},        {5,   INF, 0,   1},        {2,   INF, INF, 0}    };    floydWarshall(graph);    return 0;}

代码说明

- 我们定义了常量 V 表示顶点数，INF 表示无穷大（避免溢出，不使用 INT_MAX）。

- floydWarshall 函数接收原始图的邻接矩阵，并计算所有点对的最短路径。

- 三重循环是算法的核心：外层 k 是中间节点，内层 i 和 j 遍历所有起点和终点。

时间与空间复杂度

• 时间复杂度：O(V³)，因为有三层嵌套循环。
• 空间复杂度：O(V²)，用于存储距离矩阵。

适用场景

Floyd算法特别适合以下情况：

• 需要求解图中所有顶点对之间的最短路径（多源最短路径）。
• 图的规模不大（顶点数通常小于500），因为O(V³)的时间复杂度较高。
• 图中可能存在负权边（但不能有负权环）。

总结

通过本教程，你应该已经掌握了Floyd算法的基本原理和C语言实现方法。它是一种强大而简洁的多源最短路径算法，非常适合初学者理解动态规划在图论中的应用。记住，虽然它的复杂度较高，但在小规模图或多源查询场景下非常实用。

现在，你可以尝试修改上面的代码，输入自己的图数据，观察输出结果，加深对Floyd-Warshall算法的理解！