主題: Shortest Path Problem Single-source shortest paths Dijkstra’s algorithm Bellman-Ford algorithm All-pairs shortest paths Floyd-Warshall algorithm Transitive closure 例題講解: H.89.3 歷年題目

Shortest path 在一個 weighted 的 graph 上，一條 path 的 length 就是此 path 所經過的 edge 之 weight 總合 從 s 走到 t 所有可能的 path 中，length 最短的稱為 s-t shortest path length = 11 1 t 10 9 s 2 3 4 6 7 5 2 shortest = 9 length = 13

Negative cycle 若一個 cycle 上所有 edge 的 weight 總合是負值，則稱此 cycle 為 negative cycle 若從 s 到 t 的任何一條 path中，有一個 vertex 被包含在某個 negative cycle 中的話，則 s-t shortest path 不存在 distance = 2 distance = 1 distance = 3 distance = - 1 t 10 9 s 2 -3 4 6 7 5 2 cycle weight 總合為 -1

Single-source shortest path 給定一個 directed weighted graph 以及一個起始點 s，求 s 到其它每一個 vertex 的 shortest path (包括 path 的 length 和實際使用的 edges) 若 graph 為 undirected，可以把每條 edge 都換成兩個方向的 directed edge 若 graph 為 unweighted，則可以視為每一條 edge 的 weight 皆為 1

Example s 到 a: s  b  a distance = 8 s 到 b: s  b distance = 5 s 到 c: s  b  a  c distance = 9 s 到 d: s  b  d distance = 7 1 a c 10 9 s 2 3 4 6 7 5 b d 2

Relaxation 已知 (目前最好) 若先到 b 再到 a，是否比原來到 a 的 path 更短 s 到 a 有 length = 10 的 path s 到 b 有 length = 5 的 path b 到 a 有 weight = 3 的 edge 若先到 b 再到 a，是否比原來到 a 的 path 更短 Yes, 5 + 3 < 10 用 8 取代 10 distance = 8 distance = 10 1 a c 10 9 s 2 3 4 6 7 5 b d 2 distance = 5

Relaxation (cont.) relax(u, v): 試著用 u 目前最好的答案去修改 neighbor v 目前最好的答案 比較 distance[u] + weight(u, v)和 distance[v] 的大小 如果比 v 原本的 distance 要短，則更新 v 的 distance 1 a c 10 9 s 2 3 4 6 7 5 b d 2 distance = 5

Dijkstra’s algorithm 注意: 此方法只適用於 graph 上所有 edge 的 weight 皆不為負數的情況 用 set S 記錄已經找到 shortest path 的 vertices 每回合從 S 之外挑離 s 最近的 vertex u 加入 S 用此 vertex u 對其 neighbors 作 relax

Initialization s 一開始的 distance 為 0 其他 vertices 的 distance 皆設為  S 為空集合 1 a c 10 9 s 2 3 4 6 7 5 b d 2  

Phase 1 S 以外 distance 最小的 vertex 就是 s 將 s 放進 S 用 s 對其 neighbors 作 relax 10   1 a c 10 9 s s 2 3 4 6 7 5 b d 2  5 

Phase 2 S 以外 distance 最小的 vertex 是 b 將 b 放進 S 用 b 對其 neighbors 作 relax 8  10  14 1 a c 10 9 s s 2 3 4 6 7 5 b b d 2 5 5  7 

Phase 3 S 以外 distance 最小的 vertex 是 d 將 d 放進 S 用 d 對其 neighbors 作 relax 10 8  13 14 1 a c 10 9 s s 2 3 4 6 7 5 b b d d 2 5 5  7  7

Phase 4, 5 10 8 8  9 13 c s a  13 b 8 d 9 a a c c s s b b d d  5 5 2 3 1 9 7 4 6  13 b 8 d 9 1 a a c c 10 9 s s 2 3 4 6 7 5 b b d d 2  5 5  7 7

Implementation 用 adjacency matrix 來存 edges，也就是存每個 vertex 到 neighbor 的 edge weight S 陣列: S[i] 記錄 vertex i 是否屬於 set S distance 陣列: distance[i] 記錄 vertex i 和 s 之間目前最好的答案

Analysis 需要做 n 回合，每回合要做 總共需要 O(n2) 的時間 找到最近的 vertex u: O(n) scan S 找不在 S 內且 distance 最小的 vertex 將 u 加入 S，並 relax u 的 neighbors: O(n) scan u 在 adjacency matrix 中的那個 row 總共需要 O(n2) 的時間 有 O(m + n lg n) 的 implementation (m 為 edge 的總數)，但程式不容易寫

Shortest path tree 1 a c 若 v 最後是被 u relax 的，表示 v 的 shortest path 先到 u 才到 v pred 陣列: pred[i] 記錄從 s 到 i 的 shortest path 上，i 的前一個 vertex 是誰 循著 pred link 可以找出每個人的 shortest path，每個人的 link 合起來會變成 shortest path tree s 3 5 2 b d root s 5 b pred. link 2 3 d a 1 c

Shortest path tree construction relax(u, v) { if (distance[v] > distance[u] + weight(u, v)) { distance[v] = distance[u] + weight(u, v); pred[v] = u; } } Path construction: backtracking by using pred[]

例題講解: H. 89. 3 (http://www. cc. nccu. edu 某城市中有數條公車及捷運路線，不同路線之間可能有交會點以供轉乘，轉乘公車需要 5 分鐘，轉乘捷運需要 10 分鐘 (就算公車轉公車或捷運轉捷運也一樣) 給予每條路線上車站與車站間的行車時間，求出從起點 1 號站到其他所有車站費時最少的乘車方式

Sample input a 1 5 2 3 3 0 b 4 8 5 0 c 2 3 3 6 5 0 A 2 8 4 0 B 2 10 5 0 路線代號 (小寫為捷運) 3 c 2 號站，到下一站需 3 分鐘 5 a 3 a 1 2 3 10 8 A 6 c B 需 0 分鐘 為終點站 4 5 8 b 路線代號 (大寫為公車)

Sample output 1=>2 (0 transfer, 5 min.) 1-> 2 (a, 5 min.) 1=>3 (0 transfer, 8 min.) 1->2 (a, 5 min.) 2->3 (a, 3 min.) 1=>4 (1 transfer, 18 min.) 1->2 (a, 5 min.) a->A (5 min.) 2->4 (A, 8 min.) … 到 2 號站的資料 到 3 號站的資料 到 4 號站的資料 包括轉乘次數，花費時間，以及經過的路線和轉乘路線

解題技巧 用 shortest path 去做的話，問題點如下: 任兩點間可能有一條以上的 edges，無法用 adjacency matrix 存放 在同一點上需要轉乘，但是一個 vertex 無法表現出轉乘所需的時間 把現在的路線圖轉換成可以直接進行 shortest path 的 graph

解題技巧 (cont.) 當一個 vertex v 被好幾條路線經過時，把每條路線上的 v 都當成一個獨立的 vertex 1 2 3 1 a 5 a 2a 3a 5 a 3 a 3 c 1 2 3 1 2c 3c 2B 10 2A 8 A 6 c B 6 c 8 A 4 5 4A 8 b 5b 8 b 4b 5c 10 5B B

解題技巧 (cont.) 因為一個 vertex 被拆成好幾部分，所以可以把在同一站轉乘所花的時間放在各部分之間 到小寫字母  轉捷運花 10 分鐘 到大寫字母  轉公車花 5 分鐘 10 10 1 2a 2c 3a 3c 5b 10 10 10 10 10 10 10 10 5 10 5 5 5 5 10 10 5c 5B 5 2A 2B 4A 4b 5 5 5

Bellman-Ford algorithm 注意: 此方法可適用於 graph 上有 edge weight 為負數的情況 當 graph 中沒有 negative cycle 時，會算出從 s 到其他 vertex 的 shortest path 若 graph 中有 negative cycle，則此 algorithm 會偵測到有 negative cycle 的存在，但是不會算出正確的 shortest path 由於使用此方法的機會極少，這裡只列做法，並不講解內容

Algorithm Initialization: 設 distance[s] = 0，其他所有 vertex 的 distance 都設為  執行下述動作 n – 1 回合 Scan 此 graph 的 adjacency matrix，每看到一條 edge (u, v) 存在，就 call relax(u, v) 來更新 v 目前最好的答案 Scan 和 relax 的動作再執行一回合，但在這回合內若有 vertex 接受 relax 更新答案，則存在 negative cycle 每回合需要 O(n2) 時間，所以總共要花 O(n3) 時間

解說 若 s 到某一個 vertex v 的 shortest path 需要經過 i 條 edges，則此 shortest path 會在第 i 回合被找出 (v 在第 i 回合被 shortest path 上的前一個 vertex relax) 在 graph 上一條 shortest path 最多只會經過 n – 1 條 edges，故若沒有 negative cycle，只需要 n – 1 回合就確定找到所有 vertices 的 shortest path 若有 negative cycle 存在，則 cycle 上每個 vertices 的 distance 會隨著回合不斷減少  在第 n 回合可以檢查出來是否有人減少

All-pairs shortest path 給定一個 directed weighted graph，對所有 pair (u, v)，求 u 到 v 的 shortest distance 以及 shortest path 可以用 graph 中的每一個 vertex 當起始點來跑 single-source shortest path O(n3)

Floyd-Warshall algorithm 注意: 此方法只適用於 graph 上所有 edge 的 weight 皆不為負數的情況 注意: 這個方法是一個容易 coding 的 DP解，雖然一樣可以做 backtracking，但是 backtracking 的步驟比較麻煩，所以若需要建 shortest tree，建議使用 Dijkstra’s algorithm，這裡省略 backtracking 的部分

id 在 1 到 k 之間的所有 vertices 所形成的 graph Recurrence 令 d[i, j, k] 代表當從 i 到 j 的 path 只能經過 id 從 1 ~ k 的 vertices 時 (不含 i 和 j)，此時從 i 到 j 最短的 distance k 1 2 i j … 5 4 3 id 在 1 到 k 之間的所有 vertices 所形成的 graph

Optimal substructure 只能用 vertex id 在 1 ~ k 之間的 shortest path 有兩種可能: 這條 shortest path 所使用的 vertex 其 id 都在 1 ~ k – 1 之間，沒有用到 vertex k 表示 d[i, j, k] = d[i, j, k–1] 1 k-1 … i j 2 5 3 k

Optimal substructure (cont.) 這條 shortest path 有使用到 vertex k，也就是從 i 先到 k，再從 k 到 j 從 i 到 k 的 path 必為 i 到 k 的 shortest path，而且中間沒有使用 vertex k 這段 path 的長度為 d[i, k, k–1] 從 k 到 j 的 path 必為 k 到 j 的 shortest path，而且中間沒有使用 vertex k 這段 path 的長度為 d[k, j, k–1] 兩者合起來的長度為 d[i, k, k–1] + d[k, j, k–1]

Recurrence (cont.) d[i, j, k] = min{d[i, j, k–1], d[i, k, k–1] + d[k, j, k–1]} Boundary condition: d[i, j, 0] = w(i, j) w[i, j] 為 i 到 j 的 edge weight，若 i 到 j 沒有 edge，則為  All-pairs shortest path 的答案在 d[i, j, n]

Analysis 由於 d[i, j, k] 只需要 d[*, *, k–1] 的值，故填表順序不拘，只要 k 由小到大即可 這是一個三維的 DP recurrence，每個值只要 O(1) 的時間，所以共需 O(n3) 時間 實際上這個 algorithm 可以加以簡化，不需要開三維的陣列，只要二維陣列即可

簡化的 Warshall for k = 1 ~ n for i = 1 ~ n for j = 1 ~ n d[i, j] = min{d[i, j], d[i, k] + d[j, k]}; 由於這段 code 極易寫，所以當 n 在 1000 以下而且不需 backtrack 時，即使要做的是 single-source shortest path，也只需要寫 Warshall，不要浪費時間寫 Dijkstra

Transitive closure Transitive closure 的問題是給定一個 directed graph，要知道每一對 pair (u, v) 之間有沒有 path 相連 跟 all-pairs shortest path 問題差在是否為 shortest path 而已 可以跑 n 個 DFS 來解決此問題  O(n3)

Transitive closure (cont.) t[a, d] = True  a 有 path 通到 d t[] s a b c d a b s T T T T T T a F T T T T b T T s c T T T T d T T c d t[d, a] = False  d 沒有 path 通到 a

Reduction 修改 adjacency matrix，使其中每條 edge 的 weight 都為 1，而沒有 edge 的部分則設為  用這組 weight 去執行 all-pairs shortest path，則任一 pair (u, v) 的結果如下: u 到 v 的 distance 不是 ，則 t[u, v] = True u 到 v 的 distance 是 ，則 t[u, v] = False

歷年題目 練習題 挑戰題 歷年題目 H.89.3 大眾運輸系統 A.318 Domino Effect http://www.cc.nccu.edu.tw/info_race89/doc/final_program.doc A.318 Domino Effect http://acm.uva.es/p/v3/318.html A.10537 Toll! Revisited http://acm.uva.es/p/v105/10537.html A.10389 Subway http://acm.uva.es/p/v103/10389.html 挑戰題 A.10246 Asterix and Obelix http://acm.uva.es/p/v102/10246.html 歷年題目 H.88.3