最短路徑演算法大全：Dijkstra 單源與 Floyd 多源完整實作指南

問題定義

在帶權連通圖 (網圖) 中尋找頂點間權值和最小的路徑。無權圖可視為權值全為 1。

• 源點：路徑起始頂點
• 終點：路徑結束頂點

Dijkstra 演算法 (迪傑斯特拉)

解決單源最短路徑：指定源點到所有其他頂點的最短路徑。要求邊權值非負。

核心邏輯

1. 初始化：P = {V0}，D[V0]=0，D[Vi]=直達權值(無直達設 ∞)
2. 重複 n-1 次：
   • 在 V-P 中選 D 值最小的頂點 Vk，加入 P
   • 更新所有 Vj∈V-P：D[Vj] = min(D[Vj], D[Vk] + arc[Vk][Vj])
   • 記錄前驅節點 P[Vj] = Vk

程式碼實作

#define MAXVEX 9
#define INFINITY 65535

typedef int PathMatrix[MAXVEX];
typedef int ShortPathTable[MAXVEX];

void ShortestPath_Dijkstra(MGraph G, int v0, PathMatrix *P, ShortPathTable *D) {
    int v, w, k, min;
    int final[MAXVEX] = {0};

    for (v = 0; v < G.numVertexes; v++) {
        final[v] = 0;
        (*D)[v] = G.arc[v0][v];
        (*P)[v] = 0;
    }
    (*D)[v0] = 0;
    final[v0] = 1;

    for (v = 1; v < G.numVertexes; v++) {
        min = INFINITY;
        for (w = 0; w < G.numVertexes; w++)
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }

        final[k] = 1;
        for (w = 0; w < G.numVertexes; w++)
            if (!final[w] && (min + G.arc[k][w] < (*D)[w])) {
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
    }
}

路徑重建

void PrintPath(PathMatrix P, int v0, int v) {
    int path[MAXVEX], top = 0;
    int cur = v;
    while (cur != v0) {
        path[top++] = cur;
        cur = P[cur];
    }
    path[top++] = v0;
    while (top--) printf("%d ", path[top]);
}

Floyd 演算法 (弗洛伊德)

解決多源最短路徑：任意頂點對之間的最短路徑。允許負權邊，但不允許負權環。

核心邏輯：動態規劃

1. 初始化：D[i][j] = 直達權值，P[i][j] = j
2. 對中介點 k = 0 到 n-1：
   • 對所有 i, j：若 D[i][k] + D[k][j] < D[i][j]，更新 D[i][j] 並 P[i][j] = P[i][k]

程式碼實作

#define MAXVEX 100

typedef int PathMatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

void ShortestPath_Floyd(MGraph G, PathMatrix *P, ShortPathTable *D) {
    int v, w, k;

    // 初始化
    for (v = 0; v < G.numVertexes; v++)
        for (w = 0; w < G.numVertexes; w++) {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w;
        }

    // Floyd 核心三層迴圈
    for (k = 0; k < G.numVertexes; k++)
        for (v = 0; v < G.numVertexes; v++)
            for (w = 0; w < G.numVertexes; w++)
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];
                }
}

路徑重建

void PrintPath_Floyd(PathMatrix P, int u, int v) {
    printf("%d ", u);
    while (u != v) {
        u = P[u][v];
        printf("-> %d ", u);
    }
}

演算法選擇指南

關鍵差異總結

• Dijkstra：貪婪策略，一次確定一個頂點的最短路徑，不可回頭
• Floyd：動態規劃，逐步允許更多中介點，可處理負權邊
• 空間：Dijkstra O(n)，Floyd O(n²)
• 路徑記錄：兩者皆用前驅矩陣 P 重建完整路徑