Dijkstra 最短路徑算法 C++ 完整實現與二維動態數組詳解

算法概述

Dijkstra 算法解決單源最短路徑問題：給定帶權有向圖（權重非負），從源點 s 到所有其他頂點的最短路徑長度及路徑本身。核心思想：貪心策略，每次將當前距離最小的「藍點」染紅，並鬆弛其出邊。

數據結構設計

• int** graph：鄰接矩陣，graph[i][j] 為邊權重，INF 表示無邊
• bool* S：紅點集合標記，true = 已確定最短路徑
• int* D：源點到各頂點的當前最短距離估計
• int* Par：前驅節點，用於重構路徑

核心代碼實現

主函數：輸入圖、調用算法、輸出結果

#include 
#include 
#include 
#include 
#include 

const int INF = 100; // 題目約定 100 表示無窮大

// 前向聲明
bool emptyBlue(const std::vector& S);
int chooseBlue(const std::vector& S, const std::vector& D);
void relax(const std::vector>& graph, 
           const std::vector& S, std::vector& D, std::vector& Par);
void addRed(std::vector& S, int n);
void initializeS(std::vector& S, int s);
void initializePar(std::vector& Par, const std::vector>& graph, int s);
void initializeD(std::vector& D, const std::vector>& graph, int s);
std::string route(int s, int d, const std::vector& Par);
void display(int s, int d, const std::vector& D, const std::vector& Par);

void Dijkstra(const std::vector>& graph, int s,
              std::vector& S, std::vector& D, std::vector& Par) {
    initializeS(S, s);
    initializePar(Par, graph, s);
    initializeD(D, graph, s);
    
    while (!emptyBlue(S)) {
        int u = chooseBlue(S, D);
        addRed(S, u);
        relax(graph, S, D, Par);
    }
}

int main() {
    int k;
    std::cout << "請輸入頂點數 k: ";
    std::cin >> k;
    
    std::vector> graph(k, std::vector(k));
    std::cout << "請輸入鄰接矩陣 (" << k << "x" << k << ")，" << INF << " 表示無邊:\n";
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < k; ++j)
            std::cin >> graph[i][j];
    
    int s;
    std::cout << "請輸入源點 (0-" << k-1 << "): ";
    std::cin >> s;
    
    std::vector S(k);
    std::vector D(k), Par(k);
    
    Dijkstra(graph, s, S, D, Par);
    
    for (int d = 0; d < k; ++d)
        display(s, d, D, Par);
    
    return 0;
}

輔助函數實現

bool emptyBlue(const std::vector& S) {
    for (bool b : S) if (!b) return false;
    return true;
}

int chooseBlue(const std::vector& S, const std::vector& D) {
    int minDist = INF, idx = -1;
    for (int i = 0; i < (int)S.size(); ++i) {
        if (!S[i] && D[i] < minDist) {
            minDist = D[i];
            idx = i;
        }
    }
    return idx;
}

void relax(const std::vector>& graph,
           const std::vector& S, std::vector& D, std::vector& Par) {
    int n = graph.size();
    for (int i = 0; i < n; ++i) {
        if (S[i]) {
            for (int j = 0; j < n; ++j) {
                if (!S[j] && graph[i][j] < INF) {
                    if (D[i] + graph[i][j] < D[j]) {
                        D[j] = D[i] + graph[i][j];
                        Par[j] = i;
                    }
                }
            }
        }
    }
}

void addRed(std::vector& S, int n) { S[n] = true; }

void initializeS(std::vector& S, int s) {
    for (int i = 0; i < (int)S.size(); ++i)
        S[i] = (i == s);
}

void initializePar(std::vector& Par, const std::vector>& graph, int s) {
    for (int i = 0; i < (int)Par.size(); ++i) {
        if (i == s) Par[i] = -1;
        else Par[i] = (graph[s][i] < INF) ? s : -1;
    }
}

void initializeD(std::vector& D, const std::vector>& graph, int s) {
    for (int i = 0; i < (int)D.size(); ++i)
        D[i] = graph[s][i];
}

std::string route(int s, int d, const std::vector& Par) {
    if (Par[d] == -1 && d != s) return "不可達";
    std::string path;
    int cur = d;
    while (cur != -1) {
        path = std::to_string(cur) + (path.empty() ? "" : " -> ") + path;
        cur = Par[cur];
    }
    return path;
}

void display(int s, int d, const std::vector& D, const std::vector& Par) {
    std::cout << s << " -> " << d 
              << " 最短距離: " << (D[d] >= INF ? "不可達" : std::to_string(D[d]))
              << " 路徑: " << route(s, d, Par) << '\n';
}

關鍵技術點：動態二維數組正確創建

原代碼使用 int** p = new int*[k] 逐行分配，現代 C++ 推薦 std::vector>：

算法複雜度

• 時間：O(V^2)（鄰接矩陣 + 線性查找最小距離），優先隊列優化可達 O(E log V)
• 空間：O(V^2) 存圖 + O(V) 輔助數組

輸出示例

0 -> 0 最短距離: 0 路徑: 0
0 -> 1 最短距離: 10 路徑: 0 -> 1
0 -> 2 最短距離: 25 路徑: 0 -> 1 -> 2
0 -> 3 最短距離: 不可達 路徑: 不可達

總結

Dijkstra 算法核心：貪心選擇 + 邊鬆弛。
現代 C++ 實現首選 vector 替代裸指針二維數組，自動資源管理、邊界安全。
路徑重構利用 前驅數組 Par 回溯，從終點倒推源點。