城市間最短距離問題：最小生成樹與最短路徑雙算法實戰

問題一：最短總距離（最小生成樹）

模型

城市 = 頂點，道路 = 邊，距離 = 權重。求連接所有城市且總長度最小的方案 → 最小生成樹（MST）。

Prim 算法（鄰接矩陣版）

1. 初始化：選定起點 0 加入集合 S，其餘頂點在 T 中，記錄各頂點到 S 的最小邊權 weight[i] 及對應鄰接點 parent[i]
2. 重複 n-1 次：從 T 中選 weight 最小的頂點 u 加入 S，累加權重，輸出邊 (parent[u], u)
3. 更新 T 中頂點 v 的 weight[v]：若 edge[u][v] < weight[v] 則更新

代碼核心

void Prim(GraphMatrix& G) {
    vector<int> weight(G.VertexNum, INF), parent(G.VertexNum, -1);
    vector<bool> inMST(G.VertexNum, false);
    weight[0] = 0; int total = 0;
    for (int i = 0; i < G.VertexNum; ++i) {
        int u = -1, minW = INF;
        for (int j = 0; j < G.VertexNum; ++j)
            if (!inMST[j] && weight[j] < minW) { minW = weight[j]; u = j; }
        inMST[u] = true; total += minW;
        if (parent[u] != -1) cout << '(' << G.Vertex[parent[u]] << ',' << G.Vertex[u] << ") ";
        for (int v = 0; v < G.VertexNum; ++v)
            if (!inMST[v] && G.EdgeWeight[u][v] < weight[v]) {
                weight[v] = G.EdgeWeight[u][v];
                parent[v] = u;
            }
    }
    cout << "\nTotal weight: " << total << '\n';
}

問題二：兩城市間最短路徑（Dijkstra）

模型

同樣的圖，求指定起點到終點的最短路徑長度及路徑本身。

Dijkstra 算法（鄰接矩陣版）

1. 初始化 dist[v] = edge[start][v]，path[v] = start（若可達），visited[start] = true
2. 重複：選未訪問且 dist 最小的 u，標記訪問
3. 鬆弛：對每個未訪問鄰居 v，若 dist[u] + edge[u][v] < dist[v]，更新 dist[v] 和 path[v] = u
4. 根據 path 回溯輸出路徑

代碼核心

void Dijkstra(GraphMatrix& G, int start) {
    vector<int> dist(G.VertexNum, INF), path(G.VertexNum, -1);
    vector<bool> vis(G.VertexNum, false);
    for (int i = 0; i < G.VertexNum; ++i) {
        if (G.EdgeWeight[start][i] < INF) {
            dist[i] = G.EdgeWeight[start][i];
            path[i] = start;
        }
    }
    dist[start] = 0; vis[start] = true;
    for (int i = 1; i < G.VertexNum; ++i) {
        int u = -1, minD = INF;
        for (int j = 0; j < G.VertexNum; ++j)
            if (!vis[j] && dist[j] < minD) { minD = dist[j]; u = j; }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 0; v < G.VertexNum; ++v)
            if (!vis[v] && G.EdgeWeight[u][v] < INF && dist[u] + G.EdgeWeight[u][v] < dist[v]) {
                dist[v] = dist[u] + G.EdgeWeight[u][v];
                path[v] = u;
            }
    }
    // 輸出路徑...
}

關鍵區別

總結

同一圖模型，不同目標對應不同經典算法。MST 關注全局連通最優，最短路徑關注局部點對點最優。掌握 Prim 與 Dijkstra 的鄰接矩陣實現，是圖論算法入門的必修課。