c语言代码邻接表实现dijkstra算法求单源最短路径
时间: 2023-11-12 12:13:55 浏览: 59
以下是使用邻接表实现Dijkstra算法求单源最短路径的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
typedef struct Edge {
int dest;
int weight;
struct Edge* next;
} Edge;
typedef struct Node {
Edge* head;
} Node;
typedef struct Graph {
int num_vertices;
Node nodes[MAX_VERTICES];
} Graph;
Graph* create_graph(int num_vertices) {
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++)
graph->nodes[i].head = NULL;
return graph;
}
Edge* create_edge(int dest, int weight) {
Edge* edge = (Edge*) malloc(sizeof(Edge));
edge->dest = dest;
edge->weight = weight;
edge->next = NULL;
return edge;
}
void add_edge(Graph* graph, int src, int dest, int weight) {
Edge* edge = create_edge(dest, weight);
edge->next = graph->nodes[src].head;
graph->nodes[src].head = edge;
}
int min_distance(int dist[], int visited[], int num_vertices) {
int min_dist = INT_MAX, min_vertex;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i] && dist[i] < min_dist) {
min_dist = dist[i];
min_vertex = i;
}
}
return min_vertex;
}
void print_solution(int dist[], int num_vertices) {
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < num_vertices; i++)
printf("%d\t%d\n", i, dist[i]);
}
void dijkstra(Graph* graph, int src) {
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];
for (int i = 0; i < graph->num_vertices; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int i = 0; i < graph->num_vertices - 1; i++) {
int u = min_distance(dist, visited, graph->num_vertices);
visited[u] = 1;
for (Edge* edge = graph->nodes[u].head; edge != NULL; edge = edge->next) {
int v = edge->dest;
int weight = edge->weight;
if (!visited[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
print_solution(dist, graph->num_vertices);
}
int main() {
int num_vertices = 5;
Graph* graph = create_graph(num_vertices);
add_edge(graph, 0, 1, 10);
add_edge(graph, 0, 4, 5);
add_edge(graph, 1, 2, 1);
add_edge(graph, 1, 4, 2);
add_edge(graph, 2, 3, 4);
add_edge(graph, 3, 2, 6);
add_edge(graph, 3, 0, 7);
add_edge(graph, 4, 1, 3);
add_edge(graph, 4, 2, 9);
dijkstra(graph, 0);
return 0;
}
```
这里实现的Dijkstra算法使用了邻接表来表示图,使用了堆排序的思想来寻找当前距离源点最近的未访问过的节点,以提高算法效率。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)