多段图最短路径向前递推C语言代码
时间: 2023-08-05 11:26:53 浏览: 51
以下是一个简单的多段图最短路径向前递推的C语言代码示例:
```c
#include <stdio.h>
#include <limits.h>
#define MAX_N 1000
#define MAX_M 100000
int first[MAX_N]; // 每个阶段中第一个节点在边数组中的下标
int next[MAX_M]; // 每条边在同一阶段的下一条边在边数组中的下标
int to[MAX_M]; // 每条边的终点节点编号
int weight[MAX_M]; // 每条边的权值
int last[MAX_N]; // 每个阶段中最后一个节点在边数组中的下标
int dist[MAX_N]; // 每个节点的最短路径长度
int path[MAX_N]; // 每个节点的最短路径上的前驱节点编号
int n, m; // 节点数和边数
int s, t; // 起点和终点
void add_edge(int u, int v, int w) {
static int idx = 0;
to[idx] = v;
weight[idx] = w;
next[idx] = first[u];
first[u] = idx++;
}
void shortest_path() {
for (int i = 1; i <= n; i++) {
dist[i] = INT_MAX;
path[i] = 0;
}
dist[s] = 0;
for (int i = first[1]; i != -1; i = next[i]) {
int v = to[i];
dist[v] = weight[i];
path[v] = s;
}
for (int i = 2; i <= t; i++) {
for (int j = first[i]; j != -1; j = next[j]) {
int v = to[j];
dist[v] = INT_MAX;
for (int k = first[i-1]; k != last[i-1]; k = next[k]) {
int u = to[k];
if (dist[u] != INT_MAX && dist[u] + weight[j] < dist[v]) {
dist[v] = dist[u] + weight[j];
path[v] = u;
}
}
}
}
}
void print_path(int v) {
if (v == s) {
printf("%d", v);
} else if (path[v] == s) {
printf("%d -> %d", s, v);
} else {
print_path(path[v]);
printf(" -> %d", v);
}
}
int main() {
scanf("%d %d %d %d", &n, &m, &s, &t);
for (int i = 1; i <= n; i++) {
first[i] = -1;
}
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
}
for (int i = 1; i <= n; i++) {
last[i] = first[i+1];
}
shortest_path();
printf("最短路径长度为:%d\n", dist[t]);
printf("最短路径为:");
print_path(t);
printf("\n");
return 0;
}
```
该代码使用邻接表存储图,并且假设所有节点的编号为1到n,起点为s,终点为t。其中,first数组、next数组、to数组、weight数组分别表示邻接表中的链式存储结构,last数组则用于计算每个阶段中最后一个节点在边数组中的下标。在shortest_path函数中,我们从第一个阶段开始,逐个阶段地计算每个节点的最短路径长度,其中向前递推的部分使用了三重循环来枚举前一阶段中所有能够到达当前节点的节点,以及当前节点能够到达的下一阶段中的所有节点。在计算过程中,我们使用了INT_MAX来表示无穷大,同时使用path数组来记录每个节点在最短路径上的前驱节点编号,以便在输出最短路径时使用。