c语言用动态规划法求多段图最短路径，简单易懂

动态规划是一种解决最优化问题的算法思想，适用于求解具有最优子结构性质的问题。多段图最短路径就是其中一种典型问题。

多段图最短路径问题可以描述为：给定一个有向无环图，每个节点有一个权值，找出从起点到终点的一条路径，路径要求经过每个节点恰好一次，且路径权值最小。

下面是使用动态规划求解多段图最短路径的基本步骤：

1. 定义状态：设f(i,j)表示从起点到第i层，经过点j的最短路径长度。

2. 状态转移方程：根据多段图的特点，可以将问题划分为若干个阶段，从而可以得到状态转移方程：
f(i,j)=min{f(i-1,k)+w(k,j)},其中k为第i-1层中的点，w(k,j)为第i-1层中点k到第i层中点j的路径长度。

3. 边界条件：f(1,1)=0，f(i,j)=INF（正无穷），其中INF为一个足够大的数。

4. 最终结果：f(n,m)，其中n为终点所在层数，m为终点的编号。

下面是使用动态规划求解多段图最短路径的C语言代码实现：

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

#define MAX_N 100 // 最大节点数
#define INF INT_MAX // 无穷大

int g[MAX_N][MAX_N]; // 图的邻接矩阵表示
int f[MAX_N][MAX_N]; // 状态数组
int n; // 节点数

int main()
{
    int m; // 终点所在层数
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            g[i][j] = INF; // 初始化邻接矩阵
    for (int i = 1; i <= m; i++) // 输入终点所在层数的节点权值
    {
        int j, w;
        scanf("%d%d", &j, &w);
        g[j][i] = g[i][j] = w;
    }
    for (int i = m + 1; i <= n; i++) // 输入其他节点的权值
        for (int j = 1; j <= n; j++)
            scanf("%d", &g[j][i]);
    // 初始化状态数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = INF;
    f[1][1] = 0; // 边界条件
    // 状态转移
    for (int i = 2; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if (g[k][j] != INF && f[i - 1][k] != INF)
                {
                    if (f[i][j] == INF || f[i][j] > f[i - 1][k] + g[k][j])
                        f[i][j] = f[i - 1][k] + g[k][j];
                }
            }
        }
    // 输出结果
    printf("%d\n", f[n][m]);
    return 0;
}

以上就是使用动态规划求解多段图最短路径的C语言代码实现。