用C语言对于一个给定的多段图,用动态规划法求起点到终点的最短路径

首先，需要将多段图转化为有向无环图，然后使用动态规划的思想来求解最短路径。

假设我们有一个多段图G=(V,E)，其中每个节点v属于某个段k，起点为s和终点为t。我们可以将多段图转化为有向无环图，方法如下：

1. 将每个段k的节点用一个虚拟节点表示。

2. 对于每个节点v，如果它在段k中，那么将它与段k+1中的所有节点相连，边权为v到该节点的权值。

3. 对于起点s和终点t，分别连接到第一段和最后一段的所有节点，边权为0。

接下来，我们可以使用动态规划来求解最短路径。我们定义d[i]表示从起点s到节点i的最短路径长度，那么有以下递推式：

d[s] = 0
d[i] = min{d[j]+w(j,i)}，其中j是i的前驱节点，w(j,i)表示从j到i的边权。

最终，d[t]即为起点到终点的最短路径长度。

以下是用C语言实现该算法的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODE 100
#define INF 0x3f3f3f3f

int graph[MAX_NODE][MAX_NODE];
int d[MAX_NODE];

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

int shortest_path(int n) {
    memset(d, INF, sizeof(d));
    d[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (graph[j][i] != INF) {
                d[i] = min(d[i], d[j] + graph[j][i]);
            }
        }
    }

    return d[n];
}

int main() {
    // 构建多段图
    int n, m;
    scanf("%d%d", &n, &m);
    memset(graph, INF, sizeof(graph));
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        graph[a][b] = w;
    }

    // 求解最短路径
    int ans = shortest_path(n);
    printf("%d\n", ans);

    return 0;
}