全源最短路问题：Floyd算法详解【经典算法，限时免费】

原创

ithorizon 8个月前 (09-03) 阅读数 96 #Python

Floyd算法详解

全源最短路问题：Floyd算法详解【经典算法，限时免费】

Floyd算法是解决全源最短路问题的一种经典算法，它的时间纷乱度为O(n^3)，适用于大规模的稀疏图。下面我们就来详细了解一下Floyd算法的原理和实现。

一、算法原理

Floyd算法的核心思想是动态规划。它通过逐步迭代，逐步找到图中所有顶点对之间的最短路径。算法的基本步骤如下：

初始时，假设图中只存在相邻顶点之间的边，其他顶点之间的距离为无穷大；

逐步考虑图中所有的顶点，更新任意两个顶点之间的最短距离；

在考虑顶点k的情况下，如果顶点i到顶点j的最短路径长度大于顶点i到顶点k再到顶点j的路径长度，那么就更新顶点i到顶点j的最短路径长度；

重复上述步骤，直到所有顶点都被考虑过，此时得到的就是图中所有顶点对之间的最短路径长度。

二、算法实现

Floyd算法的实现相对易懂，下面给出一个C语言的示例代码：


        #include <stdio.h>
        #include <limits.h>
        #define MAXV 100 // 最大顶点数
        // 初始化距离矩阵
        void init(int dist[][MAXV], int n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        dist[i][j] = 0;
                    } else {
                        dist[i][j] = INT_MAX;
                    }
                }
            }
        }
        // Floyd算法
        void floyd(int dist[][MAXV], int n) {
            for (int k = 0; k < n; k++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                            dist[i][j] = dist[i][k] + dist[k][j];
                        }
                    }
                }
            }
        }
        int main() {
            int n = 4; // 顶点数
            int dist[MAXV][MAXV];
            // 初始化距离矩阵
            init(dist, n);
        // 示例：添加边和权重
        // 边 (0,1) 的权重为 5
        // 边 (0,2) 的权重为 10
        // 边 (1,2) 的权重为 3
        // 边 (1,3) 的权重为 1
        // 边 (2,3) 的权重为 7
        dist[0][1] = 5;
        dist[0][2] = 10;
        dist[1][2] = 3;
        dist[1][3] = 1;
        dist[2][3] = 7;
            // 执行Floyd算法
            floyd(dist, n);
            // 打印导致
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][j] == INT_MAX) {
                        printf("INF ");
                    } else {
                        printf("%d ", dist[i][j]);
                    }
                }
                printf("");
            }
            return 0;
        }