动态规划法网格最短路径c语言实现

动态规划通常用于求解最优化问题，如寻找矩阵或网格中的最短路径。在C语言中，我们可以使用Dijkstra算法或Floyd-Warshall算法来解决这类问题。这里以Floyd-Warshall算法为例，它适用于所有连通图，包括负权边。

Floyd-Warshall算法步骤如下：

1. 初始化距离矩阵`dist`，其中`dist[i][j]`表示从节点i到节点j的最短路径。如果不存在直接连接，则初始化为无穷大(`INT_MAX`)。
2. 对于所有中间节点k遍历所有的起点i和终点j：
a. 如果当前路径`dist[i][k] + dist[k][j]`比已知的`dist[i][j]`更短，更新`dist[i][j]`为新的值。
3. 最终`dist[i][j]`存储的就是起点i到终点j的最短路径。

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

#include <stdio.h>
#define N 4 // 网格大小，假设为4x4

int min(int a, int b) {
    return (a < b) ? a : b;
}

void floydWarshall(int graph[N][N]) {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (graph[i][j] > graph[i][k] + graph[k][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }
}

int main() {
    int graph[N][N] = { {0, 4, 'x', 2},
                        {8, 0, 'x', 7},
                        {'x', 9, 0, 6},
                        {2, 5, 'x', 0} }; // 示例网格，'x'代表不存在的边，其他数字是代价

    floydWarshall(graph);

    printf("最短路径如下:\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][j] != INT_MAX)
                printf("(%d,%d)->(%d,%d): %d\n", i, j, i+1, j+1, graph[i][j]);
        }
    }

    return 0;
}