Dijkstra演算法：單源最短路徑完整解析與C++實現

在圖論中，單源最短路徑問題是指從給定的起始頂點出發，計算到圖中其他所有頂點的最短路徑。要深入理解 Dijkstra 演算法，首先必須掌握最短路徑的「最優子結構」性質——這是演算法正確性的理論基石。

一、最短路徑的最優子結構性質

若路徑 P(i,j) = {Vi, ..., Vk, ..., Vs, ..., Vj} 是從頂點 i 到 j 的最短路徑，其中 k 和 s 為路徑上的中間頂點，則子路徑 P(k,s) 必定是從 k 到 s 的最短路徑。

證明： 假設 P(k,s) 不是最短路徑，則存在另一條更短的路徑 P'(k,s)。將其代入原路徑可構造出更短的 P'(i,j)，與 P(i,j) 為最短路徑矛盾。得證。

二、Dijkstra 演算法核心思想

基於最優子結構，Dijkstra 提出以路徑長度遞增的順序逐步生成最短路徑。對於源頂點 V0，維護兩個集合：

• U：已確定最短路徑的頂點集合（初始為 {V0}）
• V-U：尚未確定的頂點集合

演算法步驟：

1. 從 V-U 中選取 dist 值最小的頂點 u 加入 U
2. 以 u 為中介點，更新所有鄰接頂點 v 的距離：
   dist[v] = min(dist[v], dist[u] + weight(u,v))
3. 重複直到 U = V

三、測試數據與運行結果

四、C++ 完整代碼實現

/* Dijkstra單源最短路徑 2010.8.26 */
#include <iostream>
#include <stack>
#include <climits>
#define M 100
#define N 100
using namespace std;

typedef struct node {
    int matrix[N][M]; // 鄰接矩陣
    int n;            // 頂點數
    int e;            // 邊數
} MGraph;

void DijkstraPath(MGraph g, int *dist, int *path, int v0) {
    int i, j, k;
    bool *visited = new bool[g.n];
    
    // 初始化
    for (i = 0; i < g.n; i++) {
        if (g.matrix[v0][i] > 0 && i != v0) {
            dist[i] = g.matrix[v0][i];
            path[i] = v0;
        } else {
            dist[i] = INT_MAX;
            path[i] = -1;
        }
        visited[i] = false;
    }
    path[v0] = v0;
    dist[v0] = 0;
    visited[v0] = true;

    // 擴展 n-1 次
    for (i = 1; i < g.n; i++) {
        int min = INT_MAX, u = -1;
        // 尋找未訪問的最小距離頂點
        for (j = 0; j < g.n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        if (u == -1) break; // 剩餘頂點不可達
        visited[u] = true;

        // 更新鄰接頂點距離
        for (k = 0; k < g.n; k++) {
            if (!visited[k] && g.matrix[u][k] > 0 && min + g.matrix[u][k] < dist[k]) {
                dist[k] = min + g.matrix[u][k];
                path[k] = u;
            }
        }
    }
    delete[] visited;
}

void showPath(int *path, int v, int v0) {
    stack<int> s;
    int u = v;
    while (v != v0) {
        s.push(v);
        v = path[v];
    }
    s.push(v);
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

int main() {
    int n, e;
    while (cin >> n >> e && e != 0) {
        MGraph g;
        int v0;
        int *dist = new int[n];
        int *path = new int[n];
        
        // 初始化鄰接矩陣
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                g.matrix[i][j] = 0;
        
        g.n = n; g.e = e;
        for (int i = 0; i < e; i++) {
            int s, t, w;
            cin >> s >> t >> w;
            g.matrix[s][t] = w;
        }
        cin >> v0;
        
        DijkstraPath(g, dist, path, v0);
        for (int i = 0; i < n; i++) {
            if (i != v0) {
                showPath(path, i, v0);
                cout << dist[i] << endl;
            }
        }
        delete[] dist;
        delete[] path;
    }
    return 0;
}

關鍵優化說明： 原代碼使用 malloc 分配記憶體，現代 C++ 建議使用 new/delete 並配合智慧指標；另增加了不可達頂點的檢查邏輯。