FC10-Floyd-Warshall 算法：求有向or无向图中所有顶点对之间的最短路径¶

代码实现¶

C
// Floyd-Warshall 算法：求有向/无向图中所有顶点对之间的最短路径
// 参数：
// G - 图的邻接矩阵表示
// dist[][] - 存储最短路径长度的二维数组
// path[][] - 存储路径信息的二维数组
void floyed(MGraph G, int dist[][maxsize], int path[][maxsize]) {
    // 初始化阶段：将邻接矩阵复制到距离矩阵，初始化路径矩阵
    for (int i = 0; i < G.numver; i++) {
        for (int j = 0; j < G.numver; j++) {
            dist[i][j] = G.Edge[i][j];  // 复制原始边权值
            path[i][j] = -1;           // 初始化路径矩阵，-1表示直接相连
        }
    }

    // 动态规划阶段：逐步考虑通过每个顶点的中间路径
    for (int m = 0; m < G.numver; m++) {           // m：中间顶点
        for (int s = 0; s < G.numver; s++) {       // s：源顶点
            for (int e = 0; e < G.numver; e++) {   // e：目标顶点
                // 如果通过顶点m的路径更短，则更新最短路径
                if (dist[s][m] != INT_MAX && dist[m][e] != INT_MAX && 
                    dist[s][m] + dist[m][e] < dist[s][e]) {
                    dist[s][e] = dist[s][m] + dist[m][e];  // 更新最短距离
                    path[s][e] = m;                        // 记录中间顶点
                }
            }
        }
    }
}

// 函数 printPath：输出从顶点 u 到顶点 v 的完整路径
// 参数：
// u - 起始顶点
// v - 目标顶点  
// path[][] - 路径信息矩阵
void printPath(int u, int v, int path[][maxsize]) {
    // 基础情况：如果 u 和 v 直接相连（无中间顶点）
    if (path[u][v] == -1) {
        printf("%d ", u);
        return;
    }

    // 递归情况：路径经过中间顶点 path[u][v]
    printPath(u, path[u][v], path);     // 输出从 u 到中间顶点的路径
    printPath(path[u][v], v, path);     // 输出从中间顶点到 v 的路径
}

代码逻辑解析¶

1. Floyd-Warshall 算法基本思想¶

通过动态规划求解所有顶点对之间的最短路径
核心思想：对于任意三个顶点 s, m, e，如果从 s 到 m 再到 e 的路径比直接从 s 到 e 更短，则更新最短路径

2. 关键数据结构¶

dist[][]：dist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度
path[][]：path[i][j] 表示从顶点 i 到顶点 j 的最短路径上，第一个中间顶点的索引；如果为 -1，表示直接相连

3. 算法步骤详解¶

步骤1：初始化¶

C
// 将邻接矩阵复制到距离矩阵
for (int i = 0; i < G.numver; i++) {
    for (int j = 0; j < G.numver; j++) {
        dist[i][j] = G.Edge[i][j];  // 复制原始边权值
        path[i][j] = -1;           // 初始化路径矩阵
    }
}

步骤2：动态规划更新¶

C
for (int m = 0; m < G.numver; m++) {
    for (int s = 0; s < G.numver; s++) {
        for (int e = 0; e < G.numver; e++) {
            if (dist[s][m] + dist[m][e] < dist[s][e]) {
                dist[s][e] = dist[s][m] + dist[m][e];
                path[s][e] = m;
            }
        }
    }
}

4. printPath 函数详解¶

使用递归方式输出从 u 到 v 的完整路径
如果 path[u][v] == -1，表示直接相连，只需输出 u
否则递归输出从 u 到 path[u][v] 和从 path[u][v] 到 v 的路径

时间复杂度分析¶

1. 初始化阶段¶

两层嵌套循环遍历所有顶点对
时间复杂度：O(V²)

2. 动态规划阶段¶

三层嵌套循环，每层都遍历所有顶点
时间复杂度：O(V³)

3. 总体时间复杂度¶

O(V³)，其中 V 是顶点数

空间复杂度分析¶

1. 额外空间使用¶

dist[][]：O(V²)
path[][]：O(V²)
其他局部变量：常量级别

2. 总体空间复杂度¶

O(V²)，其中 V 是顶点数

较难理解部分的说明¶

1. path 数组的含义¶

C
// path[i][j] 的含义：
// 从顶点 i 到顶点 j 的最短路径上，第一个中间顶点的索引
// 如果为 -1，表示 i 和 j 直接相连

// 举例：
// path[0][3] = 1 表示：从顶点0到顶点3的最短路径经过顶点1
// 即：0 → ... → 1 → ... → 3

2. 图解说明¶

假设无向图如下：

Text Only
1 2 3 4 5 6	`1 / \| \ 2 \| 4 \ \| / 3 边权值：1-2=2, 1-3=3, 1-4=1, 2-3=4, 3-4=5`

邻接矩阵表示：

Text Only
1 2 3 4 5	`0 1 2 3 0 0 2 3 1 1 2 0 4 ∞ 2 3 4 0 5 3 1 ∞ 5 0`

Floyd-Warshall 算法执行过程：

Text Only

初始状态：
dist = [[0,2,3,1],
        [2,0,4,∞],
        [3,4,0,5],
        [1,∞,5,0]]
path = [[-1,-1,-1,-1],
        [-1,-1,-1,-1],
        [-1,-1,-1,-1],
        [-1,-1,-1,-1]]

经过中间顶点0：
dist[1][3] = min(∞, 2+1) = 3, path[1][3] = 0
dist[2][3] = min(5, 3+1) = 4, path[2][3] = 0

经过中间顶点1：
dist[0][2] = min(3, 2+4) = 3 (不变)
dist[2][3] = min(4, 4+3) = 4 (不变)

经过中间顶点2：
dist[0][1] = min(2, 3+4) = 2 (不变)
dist[1][3] = min(3, 4+5) = 3 (不变)

经过中间顶点3：
dist[0][1] = min(2, 1+3) = 2 (不变)
dist[0][2] = min(3, 1+5) = 3 (不变)

最终结果：

Text Only
1 2 3 4 5 6 7 8	`dist = [[0,2,3,1], [2,0,4,3], [3,4,0,4], [1,3,4,0]] path = [[-1,-1,-1,-1], [-1,-1,-1,0], [-1,-1,-1,0], [-1,0,0,-1]]`

3. printPath 执行示例¶

C
// 查询从顶点1到顶点3的路径
printPath(1, 3, path);
// path[1][3] = 0 ≠ -1，所以：
// printPath(1, 0, path) → 输出 1
// printPath(0, 3, path) → 输出 0
// 最终输出：1 0 3

延伸知识点¶

1. Dijkstra 算法对比¶

C
// Dijkstra算法（单源最短路径）
void dijkstra(MGraph G, int start) {
    // 1. 初始化距离数组
    // 2. 使用贪心策略选择最近顶点
    // 3. 更新其他顶点的距离
}

特性	Floyd-Warshall	Dijkstra
目标	所有顶点对	单源
时间复杂度	O(V³)	O(V²)
适用场景	稠密图	稀疏图
支持负权边	支持	不支持

2. 优化版本 - 检测负权环¶

C
// 检测负权环
bool hasNegativeCycle(MGraph G, int dist[][maxsize]) {
    for (int i = 0; i < G.numver; i++) {
        if (dist[i][i] < 0) {
            return true; // 存在负权环
        }
    }
    return false;
}

3. 实际应用场景¶

交通导航：城市间最短路径规划
网络路由：互联网数据包转发路径选择
社交网络：人际关系的最短连接路径
生物信息学：蛋白质相互作用网络分析
金融系统：货币兑换的最优路径

4. 相关算法扩展¶

C
// 传递闭包计算
void transitiveClosure(MGraph G, bool reach[][maxsize]) {
    // 类似Floyd算法，但只判断是否可达
    for (int m = 0; m < G.numver; m++) {
        for (int s = 0; s < G.numver; s++) {
            for (int e = 0; e < G.numver; e++) {
                reach[s][e] = reach[s][e] || (reach[s][m] && reach[m][e]);
            }
        }
    }
}

5. 性能优化建议¶

C
// 针对稀疏图的优化
// 使用Johnson算法：结合Bellman-Ford和Dijkstra
void johnson(MGraph G) {
    // 1. 添加虚拟顶点，使用Bellman-Ford重新赋权
    // 2. 对每个顶点运行Dijkstra算法
    // 3. 时间复杂度：O(V² log V + VE)
}

Floyd-Warshall 算法体现了动态规划在图论中的经典应用，通过逐步考虑中间顶点来优化路径，是计算机科学中重要的图算法之一。