C语言实现Warshall

Warshall算法，也称为Floyd-Warshall算法，是一种用于求解所有顶点对之间的最短路径的动态规划方法。它主要用于解决图论中的All-Pairs Shortest Paths (APSP)问题。在C语言中实现Warshall算法，你需要创建一个二维数组来存储每个节点到其他所有节点的距离，并通过迭代更新每一步的距离。

以下是简单的C语言代码实现：

#include <stdio.h>

#define V 4 // 代表图的顶点数

void printSolution(int dist[][V], int n) {
    printf("Vertex\tDistance from Source\n");
    for(int i = 0; i < V; ++i)
        printf("%d \t %d\n", i, dist[i][i]);
    for(int i = 0; i < V; ++i)
        for(int j = 0; j < V; ++j)
            if(dist[i][j] != INT_MAX && i != j)
                printf("%d to %d \t %d\n", i, j, dist[i][j]);
}

// 动态规划函数，返回源点到所有点的最短距离
int warshallFloyd(int graph[V][V]) {
    int dist[V][V]; // 初始化距离矩阵为无穷大
    // 将所有边的距离设为1，表示源点到自身的距离
    for(int i = 0; i < V; ++i)
        for(int j = 0; j < V; ++j)
            if(i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INT_MAX;

    // 每次迭代更新距离
    for(int k = 0; k < V; ++k) { // 对于每个中间节点k
        for(int i = 0; i < V; ++i) { // 对于起点i
            for(int j = 0; j < V; ++j) { // 对于终点j
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    return dist;
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0},
                       {2, 0, 1, 5},
                       {0, 1, 0, 3},
                       {0, 0, 2, 0}};

    int dist[V][V] = warshallFloyd(graph);

    printSolution(dist, V);
    return 0;
}