利用邻接表求武汉两地铁站点间最短路径,并输出中间站点及路径总长度C语言
时间: 2024-01-21 07:02:39 浏览: 67
好的,下面是一个基于Dijkstra算法的C语言实现。假设邻接表已经构建好了,并且每个节点用一个整数表示。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_NODES 1000
struct node {
int val;
int weight;
struct node* next;
};
struct graph {
struct node* edges[MAX_NODES];
int num_nodes;
};
void add_edge(struct graph* g, int u, int v, int w) {
struct node* n = (struct node*) malloc(sizeof(struct node));
n->val = v;
n->weight = w;
n->next = g->edges[u];
g->edges[u] = n;
}
void dijkstra(struct graph* g, int start, int end, int* dist, int* prev) {
int i;
for (i = 0; i < g->num_nodes; i++) {
dist[i] = INT_MAX;
prev[i] = -1;
}
dist[start] = 0;
int visited[MAX_NODES] = {0};
int heap[MAX_NODES];
int heap_size = 0;
heap[heap_size++] = start;
while (heap_size > 0) {
int curr = heap[0];
visited[curr] = 1;
if (curr == end) {
break;
}
heap[0] = heap[--heap_size];
int i = 0;
while (1) {
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left >= heap_size) {
break;
}
int child;
if (right >= heap_size || dist[heap[left]] < dist[heap[right]]) {
child = left;
} else {
child = right;
}
if (dist[heap[child]] < dist[heap[i]]) {
int tmp = heap[child];
heap[child] = heap[i];
heap[i] = tmp;
i = child;
} else {
break;
}
}
struct node* curr_node = g->edges[curr];
while (curr_node != NULL) {
int neighbor = curr_node->val;
int weight = curr_node->weight;
if (!visited[neighbor]) {
int new_dist = dist[curr] + weight;
if (new_dist < dist[neighbor]) {
dist[neighbor] = new_dist;
prev[neighbor] = curr;
heap[heap_size++] = neighbor;
int i = heap_size - 1;
while (i > 0) {
int parent = (i - 1) / 2;
if (dist[heap[i]] < dist[heap[parent]]) {
int tmp = heap[i];
heap[i] = heap[parent];
heap[parent] = tmp;
i = parent;
} else {
break;
}
}
}
}
curr_node = curr_node->next;
}
}
}
void print_path(int* prev, int start, int end) {
int path[MAX_NODES];
int len = 0;
int curr = end;
while (curr != -1) {
path[len++] = curr;
curr = prev[curr];
}
for (int i = len - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
}
int main() {
struct graph g;
g.num_nodes = 6;
g.edges[0] = NULL;
g.edges[1] = NULL;
g.edges[2] = NULL;
g.edges[3] = NULL;
g.edges[4] = NULL;
g.edges[5] = NULL;
add_edge(&g, 0, 1, 2);
add_edge(&g, 0, 2, 4);
add_edge(&g, 1, 2, 1);
add_edge(&g, 1, 3, 5);
add_edge(&g, 2, 3, 1);
add_edge(&g, 2, 4, 3);
add_edge(&g, 3, 4, 2);
add_edge(&g, 3, 5, 5);
add_edge(&g, 4, 5, 1);
int dist[MAX_NODES];
int prev[MAX_NODES];
dijkstra(&g, 0, 5, dist, prev);
printf("Shortest path: ");
print_path(prev, 0, 5);
printf("\n");
printf("Total length: %d\n", dist[5]);
return 0;
}
```
这个示例代码实现了一个简单的图,其中节点0到节点5的最短路径为0->1->2->4->5,总长度为6。您可以根据自己的数据结构和需求进行修改。
阅读全文