經典算法研究：Dijkstra算法+斐波那契堆C語言逐步實現（上）

編輯：關於C語言

本文系列目標：從偽代碼落地到可編譯運行的C代碼。本篇完成「初始化、鬆弛、圖結構、主流程」四大模塊，斐波那契堆核心操作留待下篇專講。

一、算法四步驟對應代碼骨架


DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)  // ① 初始化頂點
2  S ← ∅
3  Q ← V[G]                         // ② 初始化優先隊列（斐波那契堆）
4  while Q ≠ ∅
5      u ← EXTRACT-MIN(Q)           // ③ 抽取最小頂點
6      S ← S ∪ {u}
7      for each v ∈ Adj[u]
8          RELAX(u, v, w)           // ④ 鬆弛（觸發 DECREASE-KEY）

二、 ① 初始化頂點


void init_single_source(Graph *G, int s) {
    for (int i = 0; i < G->n; i++) {
        d[i] = INF;      // 距離上界
        pre[i] = -1;     // 前驅節點
    }
    d[s] = 0;            // 源點距離為0
}

三、 ④ 鬆弛操作


void relax(int u, int v, Graph *G) {
    if (d[v] > d[u] + G->w[u][v]) {
        d[v] = d[u] + G->w[u][v];  // 更新最短距離
        pre[v] = u;                // 記錄前驅
        // 此處需調用斐波那契堆 DECREASE-KEY(v, d[v])
    }
}

直觀理解：原路徑 A→B 距離6，發現 A→C→B 距離5，更新 B 的距離為5，前驅改為 C。

四、 ② 優先隊列初始化與 ③ EXTRACT-MIN

斐波那契堆結構較複雜，本文先給出「最小二叉堆」版本作為教學過渡，下篇再替換為斐波那契堆。兩者介面一致：


// 最小堆數組表示：Q[0] 存堆大小，Q[1..n] 存頂點編號
// 鍵值從外部 d[] 獲取：key(Q[i]) = d[Q[i]]

void buildMinHeap(int Q[], int d[]) {
    for (int i = Q[0]/2; i >= 1; i--)
        minHeapify(Q, d, i);
}

void minHeapify(int Q[], int d[], int i) {
    int l = 2*i, r = 2*i+1, smallest = i;
    if (l <= Q[0] && d[Q[l]] < d[Q[smallest]]) smallest = l;
    if (r <= Q[0] && d[Q[r]] < d[Q[smallest]]) smallest = r;
    if (smallest != i) {
        swap(Q[i], Q[smallest]);
        minHeapify(Q, d, smallest);
    }
}

int extractMin(int Q[], int d[]) {
    if (Q[0] < 1) return -1;      // 堆下溢
    int min = Q[1];
    Q[1] = Q[Q[0]];
    Q[0]--;
    minHeapify(Q, d, 1);
    return min;
}

五、圖的鄰接表結構


#define MAX_VERTEX_NUM 20
#define INF 10000
#define NIL -1

typedef struct ArcNode {
    int adjvex;          // 目標頂點下標
    struct ArcNode *nextarc;
    int weight;          // 邊權重
} ArcNode;

typedef struct VNode {
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

六、主流程整合


void dijkstra(ALGraph G, int s, int d[], int pi[], int Q[]) {
    initSingleSource(G, s, d, pi);
    // 初始化隊列 Q[1..n] = 0..n-1，Q[0]=n
    Q[0] = G.vexnum;
    for (int i = 1; i <= Q[0]; i++) Q[i] = i-1;
    Q[1] = s; Q[s+1] = 0;  // 確保源點在堆頂

    while (Q[0] != 0) {
        buildMinHeap(Q, d);           // 每輪重建堆（教學簡化，實際應用DECREASE-KEY）
        int u = extractMin(Q, d);
        for (ArcNode *p = G.vertices[u].firstarc; p; p = p->nextarc) {
            relax(u, p->adjvex, G, d, pi);
        }
    }
}

七、下篇預告

斐波那契堆節點結構：雙向循環鏈表、child/parent/mark/degree域。
核心操作：FIB-HEAP-INSERT、FIB-HEAP-EXTRACT-MIN（合併同度樹）、FIB-HEAP-DECREASE-KEY（剪切、級聯剪切、標記機制）。
將二叉堆介面無縫替換，獲得O(V log V + E)理論複雜度。

六節點示例圖