用c语言编写程序实现求带权连接图中单源最短路径的Dijkstrc算法
时间: 2024-02-12 18:06:27 浏览: 29
好的,下面是使用C语言编写的Dijkstra算法实现单源最短路径的代码示例,具体的实现思路在代码注释中有详细说明。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定义图的最大节点数
#define MAX_VERTICES 100
// 定义无穷大值
#define INFINITY INT_MAX
// 定义边的结构体
typedef struct {
int vertex; // 边的终点
int weight; // 边的权值
} Edge;
// 定义节点的结构体
typedef struct {
Edge edges[MAX_VERTICES]; // 节点的边集
int degree; // 节点的度数
} Vertex;
// 定义图的结构体
typedef struct {
Vertex vertices[MAX_VERTICES]; // 图的节点集
int num_vertices; // 图的节点数
} Graph;
// 初始化图
void init_graph(Graph *graph, int num_vertices)
{
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
graph->vertices[i].degree = 0;
}
}
// 添加边
void add_edge(Graph *graph, int start_vertex, int end_vertex, int weight)
{
Edge edge = {end_vertex, weight};
Vertex *vertex = &graph->vertices[start_vertex];
vertex->edges[vertex->degree++] = edge;
}
// Dijkstra算法求解单源最短路径
void dijkstra(Graph *graph, int start_vertex, int *dist, int *prev)
{
int visited[MAX_VERTICES] = {0}; // 记录已访问的节点
for (int i = 0; i < graph->num_vertices; i++) {
dist[i] = INFINITY;
prev[i] = -1;
}
dist[start_vertex] = 0; // 起点到自己的距离为0
for (int i = 0; i < graph->num_vertices; i++) {
int min_dist = INFINITY;
int current_vertex = -1;
// 找到当前未访问的节点中距离最短的节点
for (int j = 0; j < graph->num_vertices; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
current_vertex = j;
}
}
if (current_vertex == -1) {
break;
}
visited[current_vertex] = 1; // 标记已访问
// 遍历与当前节点相邻的节点,更新其距离
Vertex *vertex = &graph->vertices[current_vertex];
for (int j = 0; j < vertex->degree; j++) {
Edge edge = vertex->edges[j];
int neighbor_vertex = edge.vertex;
int weight = edge.weight;
int distance = dist[current_vertex] + weight;
if (distance < dist[neighbor_vertex]) {
dist[neighbor_vertex] = distance;
prev[neighbor_vertex] = current_vertex;
}
}
}
}
// 打印最短路径
void print_path(Graph *graph, int start_vertex, int end_vertex, int *prev)
{
if (start_vertex == end_vertex) {
printf("%d", start_vertex);
} else if (prev[end_vertex] == -1) {
printf("无法到达");
} else {
print_path(graph, start_vertex, prev[end_vertex], prev);
printf(" -> %d", end_vertex);
}
}
int main()
{
Graph graph;
init_graph(&graph, 7);
add_edge(&graph, 0, 1, 2);
add_edge(&graph, 0, 4, 1);
add_edge(&graph, 1, 2, 3);
add_edge(&graph, 1, 4, 3);
add_edge(&graph, 2, 3, 1);
add_edge(&graph, 3, 4, 5);
add_edge(&graph, 3, 5, 2);
add_edge(&graph, 4, 5, 4);
add_edge(&graph, 4, 6, 6);
add_edge(&graph, 5, 6, 1);
int dist[MAX_VERTICES];
int prev[MAX_VERTICES];
dijkstra(&graph, 0, dist, prev);
printf("起点到各节点的最短距离:\n");
for (int i = 0; i < graph.num_vertices; i++) {
printf("%d -> %d: %d\n", 0, i, dist[i]);
}
printf("\n起点到各节点的最短路径:\n");
for (int i = 0; i < graph.num_vertices; i++) {
printf("%d -> %d: ", 0, i);
print_path(&graph, 0, i, prev);
printf("\n");
}
return 0;
}
```
这段代码实现的是Dijkstra算法的一个简单示例,您可以根据自己的需求进行修改和扩展。