Floyd算法：核心解析与基础实现

一、算法核心描述

Floyd算法是多源最短路径算法，用于求解图中所有顶点对之间的最短路径，核心基于动态规划思想，逻辑简洁且实现直观。

1. 核心思想

定义 dist[i][j] 为顶点 i 到顶点 j 的最短路径长度，算法通过枚举中间顶点 k 优化路径：
对于任意一对顶点 (i,j)，若经过中间顶点 k 的路径（i→k→j）比当前 dist[i][j] 更短，则更新 dist[i][j] = dist[i][k] + dist[k][j]。
本质是给所有顶点对“尝试所有可能的中转站”，逐步迭代出全局最短路径。

2. 执行步骤

1. 初始化：
   • dist 矩阵：dist[i][j] 初始为顶点 i 到 j 的直接边权重；i==j 时为0；无直接边时为无穷大（∞）。
   • path 矩阵（可选，用于回溯路径）：初始为 -1（表示无中转）。
2. 迭代优化：
   三重循环枚举所有可能的中间顶点 k、起点 i、终点 j，执行状态转移：
   若 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j] 和 path[i][j] = k（记录中转顶点）。

二、基础C语言实现

#include <stdio.h>
#include <limits.h>

#define MAX_VEX 100  // 最大顶点数
#define INF INT_MAX / 2  // 无穷大（避免加法溢出）

// 打印初始图的邻接矩阵（刚创建好的图的样子）
void PrintInitGraph(int n, int dist[][MAX_VEX]) {
    printf("=== 初始图的邻接矩阵（顶点编号0~%d） ===\n", n-1);
    printf("（∞表示无直接边，0表示自身到自身）\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                printf("∞ ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
    printf("\n");
}

// Floyd算法核心函数
void Floyd(int n, int dist[][MAX_VEX], int path[][MAX_VEX]) {
    int i, j, k;

    // 初始化path矩阵（无中转时为-1）
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            path[i][j] = -1;
        }
    }

    // 三重循环迭代优化（k为中间顶点）
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                // 经过k的路径更短，则更新
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

// 打印Floyd算法计算后的最短路径矩阵
void PrintDist(int n, int dist[][MAX_VEX]) {
    printf("=== Floyd算法计算后的最短路径矩阵 ===\n");
    printf("（值为对应顶点对的最短路径长度）\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                printf("∞ ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int n = 4;  // 4个顶点（编号0~3）
    int dist[MAX_VEX][MAX_VEX];
    int path[MAX_VEX][MAX_VEX];

    // 1. 初始化邻接矩阵（dist初始值即图的边权重）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = (i == j) ? 0 : INF;  // 自身为0，其余默认无穷大
        }
    }
    // 填充图的边（基础有向图）
    dist[0][1] = 4;   // 顶点0→1，权重4
    dist[0][2] = 11;  // 顶点0→2，权重11
    dist[1][2] = 2;   // 顶点1→2，权重2
    dist[1][3] = 5;   // 顶点1→3，权重5
    dist[2][3] = 3;   // 顶点2→3，权重3

    // 2. 打印刚创建好的初始图
    PrintInitGraph(n, dist);

    // 3. 执行Floyd算法
    Floyd(n, dist, path);

    // 4. 打印最短路径结果
    PrintDist(n, dist);

    return 0;
}

运行结果

=== 初始图的邻接矩阵（顶点编号0~3） ===
（∞表示无直接边，0表示自身到自身）
0 4 11 ∞ 
∞ 0 2 5 
∞ ∞ 0 3 
∞ ∞ ∞ 0 

=== Floyd算法计算后的最短路径矩阵 ===
（值为对应顶点对的最短路径长度）
0 4 6 9 
∞ 0 2 5 
∞ ∞ 0 3 
∞ ∞ ∞ 0 

三、时空复杂度与适用图类型

1. 复杂度

• 时间复杂度：核心为三重循环，迭代次数均为顶点数 n，故为 O(n³)。
• 空间复杂度：需存储 dist 和 path 两个 n×n 矩阵，故为 O(n²)。

2. 适用图类型

Floyd算法基于邻接矩阵实现，更适合稠密图（边数多、顶点数较少，n≤100 时效率可接受）。
支持处理有向图、无向图，也可处理带权图（权重可正可负，但不能有负权回路）；不适合顶点数多的稀疏图（O(n³) 复杂度会导致效率极低）。