最短路径动态规划C语言

最短路径问题可以使用动态规划算法来解决。在C语言中，可以使用二维数组来表示图，并使用动态规划算法计算最短路径。

以下是一个使用动态规划算法求解最短路径的示例代码：

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

#define V 4  // 图中顶点的数量

// 定义一个函数来计算最短路径
void shortestPath(int graph[V][V], int src) {
    int dist[V];  // 存储从源点到每个顶点的最短距离
    int visited[V];  // 记录顶点是否被访问过

    // 初始化距离数组和访问数组
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    // 源点到自身的距离为0
    dist[src] = 0;

    // 计算最短路径
    for (int count = 0; count < V - 1; count++) {
        int minDist = INT_MAX;
        int minIndex;

        // 找到未访问的顶点中距离最小的顶点
        for (int v = 0; v < V; v++) {
            if (visited[v] == 0 && dist[v] <= minDist) {
                minDist = dist[v];
                minIndex = v;
            }
        }

        // 标记该顶点为已访问
        visited[minIndex] = 1;

        // 更新其他顶点的最短距离
        for (int v = 0; v < V; v++) {
            if (visited[v] == 0 && graph[minIndex][v] != 0 && dist[minIndex] != INT_MAX
                    && dist[minIndex] + graph[minIndex][v] < dist[v]) {
                dist[v] = dist[minIndex] + graph[minIndex][v];
            }
        }
    }

    // 打印最短路径
    printf("顶点\t\t最短距离\n");
    for (int i = 0; i < V; i++) {
        printf("%d\t\t%d\n", i, dist[i]);
    }
}

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

    int src = 0;  // 源顶点的编号

    shortestPath(graph, src);

    return 0;
}

这段代码中，我们使用了邻接矩阵来表示图，其中`graph`数组存储了图中各个顶点之间的边权重。`shortestPath()`函数使用动态规划算法计算从源顶点到每个顶点的最短距离，并将结果打印出来。

上述示例中的图是一个无向图，边的权重用整数表示。你可以根据自己的需求修改图的结构和边的权重。