堆优化版的Dijkstra算法C语言
时间: 2024-06-17 19:07:52 浏览: 14
堆优化版的Dijkstra算法是一种用于解决单源最短路径问题的经典算法,相比于普通版的Dijkstra算法,它使用了堆来对待处理节点进行优先级排序,从而提高了算法的效率。
以下是C语言实现堆优化版Dijkstra算法的基本步骤:
1. 定义一个数组dist[]来存储从源节点到其他节点的最短路径长度,初始化为无穷大。
2. 定义一个数组visited[]来标记每个节点是否已被访问过,初始时所有节点均未被访问过。
3. 将源节点加入堆中,并将dist[src]设为0。
4. 取出堆中dist[]值最小的节点u,如果该节点已被访问过,则跳过。
5. 遍历节点u的所有邻居节点v,如果dist[u]+边权值 < dist[v],则更新dist[v]的值为dist[u]+边权值。
6. 将所有未访问过的邻居节点v加入堆中。
7. 重复执行步骤4-6,直到堆为空或者所有节点都已被访问过。
以下是堆优化版Dijkstra算法的C语言代码实现(假设图以邻接矩阵形式存储):
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE 100
#define INF 1000000
int graph[MAX_NODE][MAX_NODE]; // 邻接矩阵
int dist[MAX_NODE]; // 存储最短路径长度
int visited[MAX_NODE]; // 标记每个节点是否已被访问过
int heap[MAX_NODE]; // 堆数组
int heap_size; // 堆大小
void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
void sift_up(int i) {
while (i > 1 && dist[heap[i]] < dist[heap[i/2]]) {
swap(i, i/2);
i /= 2;
}
}
void sift_down(int i) {
int child;
while (2*i <= heap_size) {
child = 2*i;
if (child+1 <= heap_size && dist[heap[child+1]] < dist[heap[child]]) {
child++;
}
if (dist[heap[i]] > dist[heap[child]]) {
swap(i, child);
i = child;
} else {
break;
}
}
}
void push(int node) {
heap[++heap_size] = node;
sift_up(heap_size);
}
int pop() {
int node = heap;
heap = heap[heap_size--];
sift_down(1);
return node;
}
void dijkstra(int src, int n) {
int i, u, v;
for (i = 1; i <= n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0;
push(src);
while (heap_size > 0) {
u = pop();
if (visited[u]) continue;
visited[u] = 1;
for (v = 1; v <= n; v++) {
if (graph[u][v] > 0 && !visited[v]) {
if (dist[u]+graph[u][v] < dist[v]) {
dist[v] = dist[u]+graph[u][v];
push(v);
}
}
}
}
}
int main() {
int n, m, u, v, w, src;
scanf("%d %d %d", &n, &m, &src);
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
graph[i][j] = 0;
}
}
for (i = 1; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
graph[u][v] = w;
}
heap_size = 0;
dijkstra(src, n);
for (i = 1; i <= n; i++) {
printf("%d ", dist[i]);
}
printf("\n");
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)