请使用动态规划思想,利用「备忘录方法」或者「迭代递推」方法,c语言实现对多段图求最短路径问题,使用邻接表
时间: 2023-10-29 21:05:43 浏览: 55
以下是使用动态规划思想,利用备忘录方法实现对多段图求最短路径问题的C语言代码,使用邻接表:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX_NUM 100 // 顶点的最大数量
#define INF INT_MAX // 无穷大
typedef struct EdgeNode {
int adjvex; // 邻接点编号
int weight; // 权重
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
typedef struct VertexNode {
int data; // 数据域
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;
typedef struct Graph {
VertexNode adjlist[MAX_VERTEX_NUM]; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} Graph;
void CreateGraph(Graph *G) { // 创建图
int i, j, k, w;
EdgeNode *e;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入各个顶点的值:");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->adjlist[i].data);
G->adjlist[i].firstedge = NULL; // 初始化邻接表
}
printf("请输入各条边的起点、终点和权值:");
for (k = 0; k < G->arcnum; k++) {
scanf("%d%d%d", &i, &j, &w);
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->weight = w;
e->next = G->adjlist[i].firstedge;
G->adjlist[i].firstedge = e; // 添加边
}
}
void PrintGraph(Graph G) { // 输出图
int i;
EdgeNode *p;
printf("图的邻接表:\n");
for (i = 0; i < G.vexnum; i++) {
printf("%d:", G.adjlist[i].data);
p = G.adjlist[i].firstedge;
while (p) {
printf("%d(%d) ", p->adjvex, p->weight);
p = p->next;
}
printf("\n");
}
}
void MultiShortestPath(Graph G) { // 多源最短路径问题
int i, j, k, t;
int dist[MAX_VERTEX_NUM]; // 存储最短路径长度
int path[MAX_VERTEX_NUM]; // 存储最短路径
EdgeNode *p;
for (i = 0; i < G.vexnum; i++) {
dist[i] = INF; // 初始化距离为无穷大
}
dist[G.vexnum-1] = 0; // 终点的距离为0
for (k = G.vexnum-2; k >= 0; k--) { // 从后往前计算每个顶点到终点的最短路径
p = G.adjlist[k].firstedge;
while (p) {
j = p->adjvex;
if (j > k) { // j在k的后面,即k到j是一条前向边
t = p->weight + dist[j];
if (t < dist[k]) {
dist[k] = t;
path[k] = j;
}
}
p = p->next;
}
}
printf("各个顶点到终点的最短路径长度:\n");
for (i = 0; i < G.vexnum; i++) {
printf("%d ", dist[i]);
}
printf("\n各个顶点到终点的最短路径:\n");
for (i = 0; i < G.vexnum; i++) {
printf("%d ", i);
j = path[i];
while (j != 0) {
printf("%d ", j);
j = path[j];
}
printf("\n");
}
}
int main() {
Graph G;
CreateGraph(&G);
PrintGraph(G);
MultiShortestPath(G);
return 0;
}
```
其中,我们使用了一个dist数组来存储各个顶点到终点的最短路径长度,使用了一个path数组来存储各个顶点到终点的最短路径。在计算每个顶点到终点的最短路径时,我们从后往前计算,依次考虑每个顶点到终点的前向边,更新dist数组和path数组。最终输出dist数组和path数组即可。