面试题：C语言中Floyd算法核心代码实现

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

// 定义图的最大顶点数
#define MAX_VERTICES 100

// 定义图的结构体
typedef struct Graph {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

// 初始化图
void initGraph(Graph *g, int numVertices) {
    g->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (i == j) {
                g->adjMatrix[i][j] = 0;
            } else {
                g->adjMatrix[i][j] = INT_MAX;
            }
        }
    }
}

// 添加边
void addEdge(Graph *g, int src, int dest, int weight) {
    g->adjMatrix[src][dest] = weight;
    // 如果是无向图，还需要添加反向边
    g->adjMatrix[dest][src] = weight;
}

// Floyd算法
void floydWarshall(Graph *g) {
    int dist[MAX_VERTICES][MAX_VERTICES];
    int i, j, k;

    // 初始化距离矩阵
    for (i = 0; i < g->numVertices; i++) {
        for (j = 0; j < g->numVertices; j++) {
            dist[i][j] = g->adjMatrix[i][j];
        }
    }

    // 逐步尝试通过每个顶点作为中间顶点，更新最短路径
    for (k = 0; k < g->numVertices; k++) {
        for (i = 0; i < g->numVertices; i++) {
            for (j = 0; j < g->numVertices; 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];
                }
            }
        }
    }

    // 输出最短路径矩阵
    printf("最短路径矩阵:\n");
    for (i = 0; i < g->numVertices; i++) {
        for (j = 0; j < g->numVertices; j++) {
            if (dist[i][j] == INT_MAX) {
                printf("INF ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
}

你可以通过以下方式调用上述函数：

int main() {
    Graph g;
    int numVertices = 4;
    initGraph(&g, numVertices);

    addEdge(&g, 0, 1, 1);
    addEdge(&g, 0, 2, 4);
    addEdge(&g, 1, 2, 2);
    addEdge(&g, 1, 3, 5);
    addEdge(&g, 2, 3, 1);

    floydWarshall(&g);

    return 0;
}

星途面试题库

面试题：C语言中Floyd算法核心代码实现

知识考点

面试题答案