C语言实现Floyd算法

什么是Floyd算法

Floyd算法是一种用于寻找给定的加权图中多源点之间最短路径的算法，也称为Floyd-Warshall算法。 其时间复杂度为O(N^3)，适用于需要求解所有顶点对间最短路径的场景。

算法思路

Floyd算法的思路是利用动态规划的思想，通过逐步考虑添加中间顶点的方式来逐步求得顶点对间的最短路径。 也就是说，我们首先考虑只通过V1来寻找其他顶点的最短路径，然后考虑只通过V1和V2来寻找其他顶点的最短路径，以此类推，最终得到所有顶点对之间的最短路径。

下面是Floyd算法的核心代码：

void Floyd(int n, double (*a)[MAXV], double (*d)[MAXV], int (*path)[MAXV])
{
    int i, j, k;
    memcpy(d, a, sizeof(double) * MAXV * MAXV);
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

其中，n表示顶点数，a表示邻接矩阵，d表示最短路径矩阵，path表示路径记录矩阵。

示例说明

以以下的图为例，其中5表示无穷大，表示两个点没有边相连：

0  1  2  3  4
---------------
0| 0  4  5  5  5
1| 4  0  3  5  5
2| 5  3  0  1  5
3| 5  5  1  0  2
4| 5  5  5  2  0

我们可以通过以下代码来求解该图的最短路径：

#include <stdio.h>
#include <string.h>
#define MAXV 1000
#define INF 1e9

int main()
{
    int n = 5; 
    double a[MAXV][MAXV] = {
        {0, 4, 5, 5, 5},
        {4, 0, 3, 5, 5},
        {5, 3, 0, 1, 5},
        {5, 5, 1, 0, 2},
        {5, 5, 5, 2, 0},
    };
    double d[MAXV][MAXV];
    int path[MAXV][MAXV];
    memset(path, -1, sizeof(path));
    Floyd(n, a, d, path);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%.2lf ", d[i][j]);
        }
        printf("\n");
    }
    return 0;
}

输出的结果为：

0.00 4.00 5.00 5.00 5.00 
4.00 0.00 3.00 5.00 5.00 
5.00 3.00 0.00 1.00 5.00 
5.00 5.00 1.00 0.00 2.00 
5.00 5.00 5.00 2.00 0.00 

其中，d[i][j]表示从i到j的最短路径长度。