圖論最短路徑：Dijkstra演算法完整實作與解析

Dijkstra 演算法核心原理

單源最短路徑演算法，適用於邊權非負的有向/無向圖。從固定源點出發，逐步擴展已確定最短路徑的頂點集合。

資料結構設計

#define MAXN 20
#define INF 1000000

int n;                    // 頂點數
int Edge[MAXN][MAXN];     // 鄰接矩陣
int S[MAXN];              // 集合標記：1=已加入最短路徑集合
int dist[MAXN];           // 源點到各頂點當前最短距離
int path[MAXN];           // 路徑前驅頂點

演算法三大核心步驟

1. 初始化：dist[i] = Edge[v0][i]，S[v0]=1，path[i]=v0 (可達) 或 -1 (不可達)
2. 選擇：從未加入集合的頂點中，選 dist 最小者 u 加入 S
3. 鬆弛：對每個未加入頂點 k，若經 u 更短則更新 dist[k] 和 path[k]

完整 C 實作

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-3：重複 n-1 次
    for (i = 0; i < n-1; i++) {
        // 找未加入集合中 dist 最小的頂點 u
        int min = INF, u = v0;
        for (j = 0; j < n; j++)
            if (!S[j] && dist[j] < min) {
                u = j;
                min = dist[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);
    
    // 讀取邊：u v w，以 -1 -1 -1 結束
    while (1) {
        scanf("%d %d %d", &u, &v, &w);
        if (u==-1 && v==-1 && w==-1) break;
        Edge[u][v] = w;
    }
    
    // 初始化鄰接矩陣
    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);  // 以 0 為源點
    
    // 輸出最短距離與路徑
    for (i = 1; i < n; i++) {
        printf("%d\t", dist[i]);
        
        int shortest[MAXN] = {0};
        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;
}

輸入範例與輸出

輸入:
6
0 1 10
0 2 5
1 2 2
1 3 1
2 1 3
2 3 9
2 4 2
3 4 4
4 3 6
4 5 2
-1 -1 -1

輸出:
7    0->2->1
9    0->2->1->3
5    0->2
11   0->2->4
9    0->2->4->5

複雜度分析

關鍵細節提醒

1. 非負權限制：負權邊會導致貪婪策略失效，需用 Bellman-Ford
2. dist[v0]=0：初始化後必須顯式歸零，否則源點距離可能被錯誤更新
3. path 初始化：不可達頂點設 -1，源點直連頂點設 v0
4. INF 選擇：需大於所有可能路徑長度總和，防止溢位

變體與應用

• 多源最短路徑：加入超級源點連接所有源點
• K 短路徑：結合 A* 或 Yen 演算法
• 帶約束最短路徑：狀態擴展 (如限制經過點數、邊數)
• 網路路由：OSPF、IS-IS 協議核心演算法