堆优化dijkstra算法c语言

### 堆优化 Dijkstra 算法 C 语言实现

为了提高效率，可以利用最小堆来优化传统的 Dijkstra 算法。传统版本的时间复杂度为 O(V²)，而通过引入优先队列（通常由二叉堆实现），时间复杂度可降低至 O((V+E)log V)[^1]。

#### 数据结构定义
首先需要定义用于表示图的数据结构以及辅助数据结构：

#include <stdio.h>
#include <stdlib.h>

#define MAX_V 1000          /* 节点的最大数量 */
#define INFTY (1 << 28)     /* 表示无穷大 */

typedef struct {
    int v, cost;
} Edge;

// 定义边列表中的单条边
Edge M[MAX_V][MAX_V];
int d[MAX_V];              // 记录最短距离
int used[MAX_V];           // 标记访问状态

#### 构建最小堆类
接着构建一个简单的最小堆类来进行节点的选择操作：

typedef struct HeapNode {  
    int node_id;            // 结点编号   
    int distance;           // 到起点的距离    
}HeapNode;

void swap(HeapNode *a, HeapNode *b){
    HeapNode t=*a;*a=*b;*b=t;
}

/* 小根堆调整函数 */
void heapify_up(HeapNode h[], int pos){
    while(pos>0 && h[(pos-1)/2].distance > h[pos].distance){
        swap(&h[pos],&h[(pos-1)/2]);
        pos=(pos-1)/2;
    }
}
void heapify_down(HeapNode h[], int size, int pos){
    int child;
    for(;pos<size;){
        child=pos*2+1;
        if(child>=size) break;
        if(child+1<size&&h[child+1].distance<h[child].distance) ++child;
        if(h[pos].distance<=h[child].distance) break;
        swap(&h[pos],&h[child]);
        pos=child;
    }
}

#### 初始化与核心逻辑
初始化阶段设置起始顶点到自身的距离为零，并将其余所有顶点设为不可达(INFTY)；随后进入主循环直到处理完所有的可达结点为止:

void dijkstra_heap(int s,int n){
    int i,j,k,minv,u,v,cost;
    memset(d,INFTY,sizeof(d));
    memset(used,0,sizeof(used));

    // 创建并填充初始堆
    HeapNode H[MAX_V], tmp={s,0};
    H[0]=tmp;d[s]=0;
    int heap_size = 1;

    while(heap_size){
        u=H[0].node_id;
        minv=d[u];

        // 移除已确定的最近节点
        H[0]=H[--heap_size];
        heapify_down(H,heap_size,0);

        if(minv==INFTY || used[u]) continue;
        
        used[u]=true;

        // 更新相邻未确认节点的信息
        for(i=0;i<n;++i){
            if(M[u][i].cost!=INFTY&&!used[i]){
                if(d[i]>d[u]+M[u][i].cost){
                    d[i]=d[u]+M[u][i].cost;
                    
                    // 插入更新后的节点到堆中
                    tmp.node_id=i,tmp.distance=d[i];
                    H[heap_size++]=tmp;
                    heapify_up(H,heap_size-1);
                }
            }
        }
    }
}

此段代码实现了基于最小堆优化过的 Dijkstra 算法，能够更高效地计算加权无向图中最短路径问题[^3]。