使用c语言解决矩阵从左上角到右下角最短路径问题

在C语言中，解决从左上角到右下角的最短路径问题通常涉及使用动态规划算法，例如著名的Floyd-Warshall算法或Dijkstra's algorithm针对无权图，如果矩阵表示有权图则更适合使用后者。这里我们以Floyd-Warshall算法为例，因为它适用于任意带权重的网格。

**Floyd-Warshall算法：**

#include <stdio.h>
#define N 4 // 假设矩阵大小为4x4

// 计算两点之间的最短距离
int minDistance(int dist[][N], int i, int j) {
    return dist[i][j];
}

void floydWarshall(int dist[][N]) {
    for (int k = 0; k < N; k++) { // 遍历所有节点作为中介点
        for (int i = 0; i < N; i++) { // 对于每个起点
            for (int j = 0; j < N; j++) { // 对于每个终点
                if (i != k && j != k && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短路径
                }
            }
        }
    }
}

int main() {
    int mat[N][N] = {{0, 4, 2, 7},
                      {8, 0, 9, 5},
                      {1, 6, 0, 3},
                      {4, 1, 8, 0}}; // 简化后的示例矩阵
    floydWarshall(mat);
    printf("左上角到右下角的最短路径为: %d\n", mat[0][3]);
    return 0;
}

在这个例子中，`dist`数组存储了每对节点之间的最短路径。初始状态下，所有通过中介节点的路径都被视为长路径。