三維迷宮問題

給定一個三維的迷宮，起點標示為 S ，終點標示為 E ，# 代表牆壁，. 表示道路，每次移動所需時間相同，計算出從起點到終點的最短時間。

其實就是二維迷宮的推廣而已，可以同樣用 DFS 解決，此時每次可前進的方向會有 6 個，分別為前、後、上、下、左、右，而判斷邊界時也要注意 x, y, z 都要判斷。因為題目必須判斷最短時間，因此要多加一個變數 dis 來儲存當前的最短步數。

部分程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//6個方向
int dir[6][3] = {{1, 0, 0},{-1, 0, 0},{0, 1, 0},{0, -1, 0},{0, 0, 1},{0, 0, -1}},dis = 30000; 

//判斷邊界函數
bool check(int a, int b, int c, int z, int y, int x){  
    return (0 <= z && z < a && 0 <= y && y < b && 0 <= x && x < c);  
}  
  
void dfs(int a, int b, int c, int z, int y, int x, int arr[30][30][30], int vis[30][30][30],int step){  
    if(arr[z][y][x] == 'E'){  
        dis = min(dis, step);  //判斷是否為最短路徑
        return;  
    }  
    vis[z][y][x] = 1;  
    for(int i = 0; i < 8; i++){  
        int tz = z + dir[i][0];  
        int ty = y + dir[i][1];  
        int tx = x + dir[i][2];  
        if(check(a, b, c, tz, ty, tx) && vis[tz][ty][tx] == 0 && arr[tz][ty][tx] != '#'){  
            //如果不是邊界或牆壁，且沒有 visit 過就進行 DFS
            dfs(a, b, c, tz, ty, tx, arr, vis, step + 1);
        }  
    }  
    vis[z][y][x] = 0;  
}

圖的最短路徑問題

單源最短路徑 (Single Source)

確定起點，去求到其他點的最短路徑問題，根據邊的權重是否有負值必須選擇不同的演算法。

權重非負 - Dijkstra’s Algorithm

  1. 建立陣列 vis，初始值為 0 ，儲存該點是否已經確定最小距離。
  2. 建立陣列 dis，dis[S] 為 0，其他點皆為無限，代表 S 到該點目前的最小距離。
  3. 建立陣列 parent，紀錄到該點最短路徑的父節點。
  4. 從 vis = 0 的點中挑選 dis 最小的點 M，檢查其相鄰節點 N，假設 N 到 M 距離為 k ，取 dis[M] = min(dis[M] ,dis[N] + k)，並將 vis[M] 標示為 1。
  5. 重複步驟 4 直到所有點皆被 visited。

實作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//假設該圖有 n 個節點，且所有節點連通，d[a][b] 儲存 a 到 b 的權重
void dijkstra(int S){
    //初始化陣列
    for(int i = 0; i < n; i++){
        vis[i] = 0;
        dis[i] = 1e9;
    }
    dis[S] = 0;
    parent[S] = S;

    for(int i = 0; i < n; i++){
        int p, minDis = 1e9;
        for(int j = 0; j < n; j++){
            if(!vis[j] && dis[j] < minDis){
                p = j; //紀錄距離最小點
                minDis = dis[j];
            }
        }
        vis[p] = 1;
        //檢查鄰近節點
        for(int j = 0; j < n; j++){
            if(!vis[j] && dis[p] + d[p][j] < dis[j]){
                dis[j] = dis[p] + d[p][j];
                parent[j] = p;
            }
        }
    }
}

如果要取得 S 到某點 P 的最短路徑，只要從 parent[P] 開始往回推直到 S 點。

權重為負 - Bellman-ford Algorithm

  1. 建立陣列 dis，dis[S] 為 0，其他點皆為無限，代表 S 到該點目前的最小距離。
  2. 建立陣列 parent，紀錄到該點最短路徑的父節點。
  3. 窮舉 S 到所有點 A 以及其鄰近點 B，假設 A 和 B 之間距離為 k，如果 dis[A] + k < dis[B]，則進行 relax，設定 dis[B] = dis[A] + k。重複本步驟 (n - 1) 次，其中 n 為總結點數。
  4. 再次窮舉所有點進行檢查，如果可以 relax 代表存在負環。

如果存在負環代表繞了該環一圈之後權重和為負數，只要一直繞圈就會使路徑長變短。

實作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int relax(){
    int b = 0;
    //窮舉所有點
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            //檢查是否能 relax
            if (dis[j] > dis[i] + d[i][j]){
                dis[j] = dis[i] + d[i][j];
                parent[j] = i;
                updated = 1;
            }
        }
    }
    //回傳是否有進行 relax
    return updated;
}

int bellman_ford(int S){
    // 初始化陣列
    for (int i = 0; i < n; i++) dis[i] = 1e9;
    dis[S] = 0;
    //進行 n - 1 次
    for (int i = 1; i < n; i++){
        //如果無法 relax 則提前結束
        if (!relax()) break;
    }
    //檢查負環
    int neg_cycle = relax();
    return neg_cycle;
}

全域最短路徑 (All Pairs)

也稱為多源最短路問題，用於求圖中所有的最短路徑。

Floyd–Warshall Algorithm

窮舉所有節點 k ，將其作為中繼點，比較 dis[i][j] 和 dis[i][k] + dis[k][j] 的大小，如果經過 k 點會使距離更小則將其記錄下來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void floyd_warshall(){
    //初始化陣列
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            dis[i][j] = d[i][j];
        }
        dis[i][i] = 0;
    }
    //窮舉所有點 k 做為中間點
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

注意本演算法的時間複雜度為 O(n3)O(n^3) ，使用時須注意是否會超時。