在内存不超限情况,给定任意一张带权值的有向连通图,请采用Dijkstra算法输出从给定结点到其余结点的最短路径以及路径长度,给出c语言代码
时间: 2023-05-15 13:06:22 浏览: 61
以下是基于Dijkstra算法的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF INT_MAX // 定义正无穷
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点集合
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
void Dijkstra(Graph *G, int start, int *dist, int *prev) {
int i, j, k;
int min;
int visited[MAX_VERTEX_NUM]; // 标记顶点是否已访问
for (i = 0; i < G->vertex_num; i++) {
dist[i] = G->edge[start][i]; // 初始化距离
visited[i] = 0; // 标记为未访问
if (G->edge[start][i] < INF) {
prev[i] = start; // 记录前驱结点
} else {
prev[i] = -1; // 无前驱结点
}
}
dist[start] = 0; // 起点到自身的距离为0
visited[start] = 1; // 标记为已访问
for (i = 1; i < G->vertex_num; i++) {
min = INF;
for (j = 0; j < G->vertex_num; j++) {
if (!visited[j] && dist[j] < min) {
k = j;
min = dist[j];
}
}
visited[k] = 1; // 标记为已访问
for (j = 0; j < G->vertex_num; j++) {
if (!visited[j] && G->edge[k][j] < INF) {
if (dist[k] + G->edge[k][j] < dist[j]) {
dist[j] = dist[k] + G->edge[k][j]; // 更新距离
prev[j] = k; // 记录前驱结点
}
}
}
}
}
int main() {
Graph G;
int i, j, start;
int dist[MAX_VERTEX_NUM]; // 存储最短距离
int prev[MAX_VERTEX_NUM]; // 存储前驱结点
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vertex_num, &G.edge_num);
printf("请输入顶点:");
for (i = 0; i < G.vertex_num; i++) {
scanf("%d", &G.vertex[i]);
}
for (i = 0; i < G.vertex_num; i++) {
for (j = 0; j < G.vertex_num; j++) {
G.edge[i][j] = INF; // 初始化邻接矩阵
}
}
printf("请输入边及其权值:\n");
for (i = 0; i < G.edge_num; i++) {
int v1, v2, w;
scanf("%d