圖論經典：Dijkstra單源最短路徑算法C語言完整實現與核心邏輯圖解

算法背景與適用條件

Dijkstra 算法用於求解帶權有向圖中單源最短路徑，核心限制：**邊權值必須非負**。給定源點 v0，算法可計算其到圖中所有其他頂點的最短路徑長度及具體路徑。

核心數據結構：三大數組協同工作

• S[n]：標記集合，S[i]=1 表示頂點 vi 已加入最短路徑集合，初始僅 S[v0]=1。
• dist[n]：當前找到的源點到各頂點的最短路徑長度，初始 dist[i] = Edge[v0][i]（鄰接矩陣）。
• path[n]：路徑前驅記錄，path[i] 存儲 v0→vi 最短路徑上 vi 的前一個頂點，初始可達點設為 v0，不可達設為 -1。

算法三步走：貪心策略逐步擴展集合 S

1. 選點：在 dist[] 中找 S[i]!=1 且 dist[i] 最小的頂點 u。
2. 加入：置 S[u]=1，確定 v0→u 的最短路徑不再變化。
3. 鬆弛：對每個未加入集合的頂點 vk，若 u→vk 有邊且 dist[u] + Edge[u][k] < dist[k]，則更新 dist[k] 與 path[k]=u。

循環 n-1 次即可覆蓋所有頂點。

完整 C 代碼實現（鄰接矩陣版）

#include <stdio.h>
#include <string.h>
#define MAXN 20
#define INF 1000000

int n;
int Edge[MAXN][MAXN];
int S[MAXN], dist[MAXN], path[MAXN];

void Dijkstra(int v0) {
    int i, j, k;
    // 1. 初始化
    for (i = 0; i < n; i++) {
        dist[i] = Edge[v0][i];
        S[i] = 0;
        if (i != v0 && dist[i] < INF) path[i] = v0;
        else path[i] = -1;
    }
    S[v0] = 1; dist[v0] = 0;  // 源點入集合

    // 2. 主循環 n-1 次
    for (i = 0; i < n-1; i++) {
        int min = INF, u = v0;
        // 找未入集合的最近點 u
        for (j = 0; j < n; j++)
            if (!S[j] && dist[j] < min) { min = dist[j]; u = j; }
        S[u] = 1;  // 關鍵：加入集合
        // 鬆弛所有鄰接點
        for (k = 0; k < n; k++)
            if (!S[k] && Edge[u][k] < INF && dist[u] + Edge[u][k] < dist[k]) {
                dist[k] = dist[u] + Edge[u][k];
                path[k] = u;
            }
    }
}

int main() {
    int i, j, u, v, w;
    scanf("%d", &n);
    while (1) {
        scanf("%d %d %d", &u, &v, &w);
        if (u==-1 && v==-1 && w==-1) break;
        Edge[u][v] = w;
    }
    // 初始化鄰接矩陣：對角線0，無邊置INF
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j) Edge[i][j] = 0;
            else if (Edge[i][j] == 0) Edge[i][j] = INF;

    Dijkstra(0);

    // 輸出最短路徑長度與路徑
    int shortest[MAXN];
    for (i = 1; i < n; i++) {
        printf("%d\t", dist[i]);
        memset(shortest, 0, sizeof(shortest));
        int k = 0;
        shortest[k] = i;
        while (path[shortest[k]] != 0) {
            k++;
            shortest[k] = path[shortest[k-1]];
        }
        k++; shortest[k] = 0;
        for (j = k; j > 0; j--) printf("%d->", shortest[j]);
        printf("%d\n", shortest[0]);
    }
    return 0;
}

關鍵細節避坑指南

• 初始化順序：先賦值 dist[]、path[]，再單獨置 S[v0]=1, dist[v0]=0，否則源點可能被誤判為不可達。
• 找最小點：條件 !S[j] && dist[j] < min 必須同時滿足，避免重複選點或選到已確定點。
• 路徑回溯：從終點沿 path[] 逆向追溯至源點，再反序輸出。

複雜度與優化方向

鄰接矩陣版時間複雜度 O(n²)，適合稠密圖。稀疏圖建議改用鄰接表 + 優先隊列（最小堆），將選點優化至 O(log n)，總複雜度降為 O((V+E) log V)。