c语言实现动态规划 多段图求最少成本路径

动态规划是一种常用的求解最短路径问题的方法，可以用来求解多段图的最少成本路径。下面是一个使用C语言实现动态规划求解多段图最少成本路径的示例代码：

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

#define N 6 // 图中顶点的个数
#define M 7 // 图中边的个数

// 定义图的边结构
typedef struct {
    int u; // 边的起点
    int v; // 边的终点
    int w; // 边的权重
} Edge;

// 动态规划求解多段图最少成本路径
void shortestPath(Edge edges[], int dist[], int path[]) {
    // 初始化距离数组和路径数组
    for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    
    // 设置终点的距离为0
    dist[N-1] = 0;
    
    // 从后往前计算每个顶点的最短路径
    for (int i = N-2; i >= 0; i--) {
        // 遍历所有边，找到以当前顶点为起点的边
        for (int j = 0; j < M; j++) {
            if (edges[j].u == i) {
                // 计算当前顶点到边的终点的距离
                int newDist = edges[j].w + dist[edges[j].v];
                // 更新最短路径和路径数组
                if (newDist < dist[i]) {
                    dist[i] = newDist;
                    path[i] = edges[j].v;
                }
            }
        }
    }
}

int main() {
    // 定义图的边数组
    Edge edges[M] = {
        {0, 1, 2},
        {0, 2, 4},
        {1, 3, 3},
        {1, 4, 2},
        {2, 3, 1},
        {2, 4, 3},
        {3, 5, 2}
    };
    
    // 定义距离数组和路径数组
    int dist[N];
    int path[N];
    
    // 求解最短路径
    shortestPath(edges, dist, path);
    
    // 输出最短路径和最短距离
    printf("最短路径：");
    int v = 0;
    printf("%d", v);
    while (path[v] != -1) {
        v = path[v];
        printf(" -> %d", v);
    }
    printf("\n最短距离：%d\n", dist[0]);
    
    return 0;
}