Advanced Competitive Programming

Presentation on theme: "Advanced Competitive Programming"— Presentation transcript:

1 Advanced Competitive Programming
國立成功大學ACM-ICPC程式競賽培訓隊 Department of Computer Science and Information Engineering National Cheng Kung University Tainan, Taiwan

2 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

3 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

4 Graph 圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構。

5 Graph 圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構。 G = (E, V) 為圖

6 Graph 點 (vertex)： 組成圖的最基本元素

7 Graph u v 點 (vertex)： 組成圖的最基本元素 邊 (edge)： 點與點的關係 通常用 u 表示邊的起端，v 表示邊的終端

8 Graph 點 (vertex)： 組成圖的最基本元素 邊 (edge)： 點與點的關係
通常用 u 表示邊的起端，v 表示邊的終端 有向圖 (directed graph)： 邊帶有方向性 u -> v，表示 u 能走到 v，但 v 不保證走到 u

9 Graph 點 (vertex)： 組成圖的最基本元素 邊 (edge)： 點與點的關係
通常用 u 表示邊的起端，v 表示邊的終端 有向圖 (directed graph)： 邊帶有方向性 u -> v，表示 u 能走到 v，但 v 不保證走到 u 無向圖 (undirected graph)： 每條邊都是雙向的 u <-> v，表示 v 能到 u，u 能到 v

10 Graph 道路 (walk)： 點邊相間的序列

11 Graph 道路 (walk)： 點邊相間的序列 e.g.  v0e1v1e2v2...envn

12 Graph 道路 (walk)： 點邊相間的序列 e.g.  v0e1v1e2v2...envn 路徑 (path)： 點不重複的道路

13 Graph 道路 (walk)： 點邊相間的序列 e.g. v0e1v1e2v2...envn 路徑 (path)： 點不重複的道路
環 (cycle)： 把路徑的起點與終點連接起來

14 Graph 道路 (walk)： 點邊相間的序列， e.g. v0e1v1e2v2...envn 路徑 (path)： 點不重複的道路
環 (cycle)： 把路徑的起點與終點連接起來 走訪/遍歷 (traversal/search)： 走完全部的點或邊

15 該怎麼表示一張圖呢

16 Graph 鄰接矩陣 用二維陣列表達點與點有無邊關係 E[u][v] = 1 表示 u 與 v 間有邊

17 Graph 鄰接矩陣 用二維陣列表達點與點有無邊關係 用特殊的值來表示無法到達的情況 E[u][v] = 1 表示 u 與 v 間有邊
例如 INT_MAX 或是 -1 或是 INF

18 Graph 鄰接表 vector<int> E[maxv]; to = E[from][0]; from to

19 Graph 鄰接表 E[2][0] = 3; 2 3

20 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; 2 9 8 3

21 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; E[2][1] = 9; 2 9 8 3

22 2 9 8 3 7 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; E[2][1] = 9;

23 2 9 5 8 3 1 7 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; E[2][1] = 9;

24 2 9 5 8 3 1 7 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; E[2][1] = 9;

25 2 9 5 8 3 1 7 Graph 鄰接表 E[2][0] = 3; E[8][0] = 9; E[2][1] = 9;

26 Tree Tree 是一個有向無環連通圖

27 Tree Tree 是一個有向無環連通圖 節點 (node)： 一般樹上的點

28 Tree Tree 是一個有向無環連通圖 節點 (node)： 一般樹上的點 父 (parent)： 節點能反向拜訪的第一個節點
子 (child)： 節點能正向拜訪的第一個節點

29 Tree Tree 是一個有向無環連通圖 節點 (node)： 一般樹上的點 父 (parent)： 節點能反向拜訪的第一個節點
子 (child)： 節點能正向拜訪的第一個節點 根 (root)： 沒有父節點的節點 葉 (leaf)： 沒有子節點的節點

30 Tree 每個點都是節點 根 G的父 B的子 葉 葉 葉 葉 葉 葉

31 Tree 祖先 (ancestor)： 節點能反向拜訪的所有節點 孫子 (descendant)： 節點能正向拜訪的所有節點

32 Tree 祖先 (ancestor)： 節點能反向拜訪的所有節點 孫子 (descendant)： 節點能正向拜訪的所有節點
深度 (depth)： 從根到該節點所經過的邊數

33 Tree 祖先 (ancestor)： 節點能反向拜訪的所有節點 孫子 (descendant)： 節點能正向拜訪的所有節點
深度 (depth)： 從根到該節點所經過的邊數 森林 (forest)： 一個集合包含所有不相交的 Tree 每個非根節點只有一個父節點

34 Tree

35 Tree

36 Tree G的Depth為2

37 Tree G的祖先

38 Tree G的孫子

39 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

40 Minimum spanning tree

41 生成樹 給定連通圖 G = (E, V) 使用 E 子集連接所有的點 (屬於 V) 所得到的樹

42 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

43 9 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

44 16 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

45 20 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

46 21 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

47 24 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

48 29 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

49 30 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

50 38 生成樹 1 8 3 9 6 1 5 8 3 7 2 4

51 38 生成樹 1 3 9 1 5 8 7 4

52 最小生成樹 給定連通圖 G = (E, V) 在所有生成樹中，找到邊權重總和最小的生成樹

53 29 最小生成樹 8 1 3 6 5 9 1 8 7 2 4

54 29 最小生成樹 8 1 3 6 5 1 2

55 兩個重要前提 樹是無環的連通圖 若圖只有點無任何邊，那每點都是彼此獨立連通塊

56 46 無環連通圖 8 3 9 6 1 8 7 4

57 兩個重要前提 樹是無環的連通圖 若圖只有點無任何邊，那每點都是彼此獨立連通塊

58 獨立的連通塊們

59 最小生成樹 Kruskal 演算法 Prim 演算法

60 最小生成樹 Kruskal 演算法 Prim 演算法

61 Kruskal 演算法 在產生生成樹以前，所有點都為獨立的連通塊 若兩個獨立的連通塊相連，整個圖就少一連通塊

62

63 1 1

64 如何產生生成樹 在連通塊 A 與連通塊 B 相連時確保不會產生環 最終就能得到一棵生成樹

65 1 1

66 5 1 4

67 12 1 7 4

68 20 1 8 7 4

69 23 3 1 8 7 4

70 31 8 3 1 8 7 4

71 40 8 3 9 1 8 7 4

72 46 8 3 9 6 1 8 7 4

73 怎樣不產生環 在連通塊 A 與連通塊 B 相連時確保不會產生環 A ≠ B ⟺ 加入新的邊不產生環

74 23 A 連通塊 1 8 3 6 5

75 23 B 連通塊 1 8 3 6 5

76 23 相連 1 8 3 9 6 5

77 32 相連 1 8 3 9 6 5

78 (☉д⊙) 產生環 3 5

79 怎樣不產生環 在連通塊 A 與連通塊 B 相連時確保不會產生環 A ≠ B ⟺ 加入新的邊不產生環

80 怎樣不產生環 在連通塊 A 與連通塊 B 相連時確保不會產生環 A ≠ B ⟺ 加入新的邊不產生環 所以過程中要確保挑的連通塊互為獨立

81 Kruskal 演算法 直覺的，每次相連選一個合法且權重最小的邊 最終得到的生成樹，就是最小生成樹

82 Kruskal 1 8 3 9 6 1 5 8 3 7 2 4

83 權重排序 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

84 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

85 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

86 1 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

87 1 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

88 1 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

89 2 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

90 2 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

91 2 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

92 4 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

93 4 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

94 4 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

95 7 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

96 7 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

97 7 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

98 10 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

99 10 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

100 10 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

101 (☉д⊙) 環 1 1 2 3 4 5 6 7 8 9 8 3 9 6 5 8 7

102 10 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

103 10 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

104 10 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

105 15 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

106 15 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

107 15 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

108 21 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

109 21 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

110 21 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

111 (☉д⊙) 環 1 1 2 3 4 5 6 7 8 9 8 3 9 6 5 8 3 4

112 21 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

113 21 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

114 21 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

115 (☉д⊙) 環 1 1 2 3 4 5 6 7 8 9 8 3 9 1 3 7 2 4

116 21 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

117 21 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

118 21 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

119 29 相連 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

120 29 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

121 29 檢查 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

122 (☉д⊙) 環 1 2 3 4 5 6 7 8 9 3 1 5 8 3 7 2 4

123 29 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

124 29 遍歷完成 1 1 2 3 4 5 6 7 8 9 8 3 9 6 1 5 8 3 7 2 4

125 29 最小生成樹 1 8 3 6 1 5 3 2

126 Kruskal 實作 若使用 DFS 判斷兩點是否屬於同個連通塊 則最終複雜度為 O(|E|2) 枚舉每個邊 O(|E|)

127 Kruskal 實作 是否為同個連通塊，是一個分類問題 兩連通塊獨立 ⟺ 彼此間沒有重複的點

128 Kruskal 實作 是否為同個連通塊，是一個分類問題 兩連通塊獨立 ⟺ 彼此間沒有重複的點

129 Kruskal 實作 是否為同個連通塊，是一個分類問題 兩連通塊獨立 ⟺ 彼此間沒有重複的點
也就是說，連通塊們是個 Disjoint Sets 可以用 Union-Find Forest 改善複雜度 第四週教材中有 Union-Find Forest 的介紹

130 Kruskal 實作 bool cmp(const edge &A, const edge &B) { return A.w < B.w; }

131 Kruskal 實作 vector<edge> E; // 邊集合 : . sort(E.begin(), E.end(), cmp); for (edge e: E) { int a = Find(e.u), b = Find(e.v); if (a != b) { Union(e.u, e.v); cost += E.w; MST.emplace_back(u, v, w); } }

132 Kruskal 實作 用 Union-Find Forest 改善複雜度 複雜度為 O(|E|log2|E| + |E|⋅ α)

133 Questions?

134 練習 UVa OJ Arctic Network AIZU 1280 Slim Span

135 最小生成樹 Kruskal 演算法 Prim 演算法

136 Prim 演算法 很類似的

137 兩個重要前提 樹是無環的連通圖 若圖只有點無任何邊，那每點都是彼此獨立連通塊

138 Prim 演算法 Prim 維護一個未完成的生成樹

139 Prim 演算法 Prim 維護一個未完成的生成樹 每次將樹周遭有最小權重的邊接到樹上， 使樹最終成長至最小生成樹

140 1 8 3 9 6 1 5 8 3 7 2 4

141 Prim 演算法 先隨便的挑任意點

142 1 8 3 9 6 1 5 8 3 7 2 4

143

144 Prim 演算法 先隨便的挑任意點 使它為初始的未完成的生成樹

145 Prim 演算法 先隨便的挑任意點 使它為初始的未完成的生成樹，稱它為 MST 明顯的，它是個無環連通圖

146 1 8 3 9 6 1 5 8 3 7 2 4

147 MST

148 Prim 演算法 直覺的，每次將 MST 周遭權重最小的邊接上去 那麼最終產生的生成樹為最小生成樹

149 1 8 3 9 6 1 5 8 3 7 2 4

150 6 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

151 6 MST 6

152 6 1 8 3 9 6 1 5 8 3 7 2 4

153 7 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

154 7 MST 1 6

155 7 1 8 3 9 6 1 5 8 3 7 2 4

156 10 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

157 10 MST 1 3 6

158 10 1 8 3 9 6 1 5 8 3 7 2 4

159 15 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

160 15 MST 1 3 6 5

161 15 1 8 3 9 6 1 5 8 3 7 2 4

162 23 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

163 23 MST 1 8 3 6 5

164 23 1 8 3 9 6 1 5 8 3 7 2 4

165 24 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

166 24 MST 1 8 3 6 1 5

167 24 1 8 3 9 6 1 5 8 3 7 2 4

168 26 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

169 26 MST 1 8 3 6 1 5 2

170 26 1 8 3 9 6 1 5 8 3 7 2 4

171 29 周圍最小邊 1 8 3 9 6 1 5 8 3 7 2 4

172 29 MST 1 8 3 6 1 5 3 2

173 Prim 實作 struct node { int id; // 點的編號 int w; // 連結到此點的權重 (邊權重) };

174 Prim 實作 vector<node> E[maxv]; // maxv 為最大節點數 : . /* 假設輸入完邊的資訊了 */

175 Prim 實作 /* 每次挑最小權重的邊 */ priority_queue<edge> Q; /* 初始的生成樹 (只有一個點) */ Q.push({1, 1, 0});

176 Prim 實作 while(!Q.empty()) { edge e = Q.top(); Q.pop(); int u = e.v; if(!vis[u]) { // 避免出現環 MST.push_back(e); cost += e.w; for(auto v: E[u]) if(!vis[v.id]) Q.push({u, v.id, v.w}); } vis[u] = true; }

177 Prim 實作 跟 Kruskal 比較 Prim 枚舉的是點 Kruskal 枚舉的是邊 其複雜度為 O(|E|log2|V|)

178 Questions?

179 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

180 Single-Source Shortest Paths

181 SSSP 給定 源點/起點(Source) 問每條路徑的最小成本 源點到各點的最小總成本

182 SSSP Breadth-First Search Relaxation Dijkstra's algorithm
Bellman-Ford's algorithm

183 SSSP Breadth-First Search Relaxation Dijkstra's algorithm
Bellman-Ford's algorithm

184 廣度優先搜尋

185 BFS 廣度優先搜尋 (Breadth-First Search) 簡稱 BFS a c p k o f g h i l z j

186 BFS 程式碼 queue<int> Q; Q.push(source); vis[source] = true; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; Q.push(v); }

187 BFS 的點遍歷順序 a c p k o f g h i l z j

188 BFS 的點遍歷順序 1 2 3 4 5 6 7 8 9 A B C

189 第一個拜訪的為根 藍色為未曾拜訪 1 c p k o f g h i l z j

190 拜訪所有鄰點 黃色為拜訪中 1 2 p k o f g h i l z j

191 拜訪所有鄰點 1 2 3 k o f g h i l z j

192 拜訪所有鄰點 1 2 3 4 o f g h i l z j

193 拜訪所有鄰點 1 2 3 4 5 f g h i l z j

194 根拜訪完 紫色為拜訪完 1 2 3 4 5 f g h i l z j

195 拜訪所有鄰點 1 2 3 4 5 6 g h i l z j

196 拜訪所有鄰點 1 2 3 4 5 6 7 h i l z j

197 拜訪完 1 2 3 4 5 6 7 h i l z j

198 拜訪所有鄰點 1 2 3 4 5 6 7 8 9 A B j

199 拜訪完 1 2 3 4 5 6 7 8 9 A B j

200 拜訪完 1 2 3 4 5 6 7 8 9 A B j

201 拜訪完 1 2 3 4 5 6 7 8 9 A B j

202 拜訪完 1 2 3 4 5 6 7 8 9 A B j

203 拜訪完 1 2 3 4 5 6 7 8 9 A B j

204 拜訪所有鄰點 1 2 3 4 5 6 7 8 9 A B C

205 拜訪完 1 2 3 4 5 6 7 8 9 A B C

206 拜訪完 1 2 3 4 5 6 7 8 9 A B C

207 拜訪完 1 2 3 4 5 6 7 8 9 A B C

208 拜訪完 1 2 3 4 5 6 7 8 9 A B C

209 拜訪完 1 2 3 4 5 6 7 8 9 A B C

210 BFS 樹 1 2 3 4 5 6 7 8 9 A B C

211 BFS 樹 1 2 3 4 5 6 7 8 9 A B C

212 S 到 T S T

213 BFS 完 S T

214 BFS 完 S T

215 3 深度/成本: 3 S T

216 若邊權重 ≥ 1 1 8 3 4 6 1 5 8 3 7 S 2 T 4

217 若邊權重 ≥ 1 怎麼辦?

218 將權重切段 例如 x 權重，切成共 x 段的 1 權重邊

219 將權重切段 例如 3 權重 3

220 將權重切段 例如 3 權重，切成共 3 段的 1 權重邊 1 1 1

221 將權重切段 例如 3 權重，切成共 3 段的 1 權重邊 就能 BFS 了! 1 1 1

222 將權重切段 例如 3 權重，切成共 3 段的 1 權重邊 就能 BFS 了! 複雜度肯定會爆炸!

223 Questions?

224 單源最短路徑 Relaxation Dijkstra's algorithm Bellman-Ford's algorithm

225 單源最短路徑 Relaxation Dijkstra's algorithm Bellman-Ford's algorithm

226 Relaxation 想像自己是圖中的某點 v v

227 Relaxation u u 想像自己是圖中的某點 v 身旁有一些鄰點 u v u

228 Relaxation 14 5 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 9

229 Relaxation 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) 8 v 6 9

230 Relaxation 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 6 9

231 Relaxation 23 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 6 9

232 Relaxation 23 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 6 9

233 Relaxation 23 13 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 6 9

234 Relaxation 23 13 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 6 9

235 Relaxation 23 13 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 8 v 15 6 9

236 Relaxation 23 13 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 v 就能得知，源點到 v 的最小成本 8 v 15 6 9

237 Relaxation 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 v 就能得知，源點到 v 的最小成本 8 v 6 9

238 Relaxation 14 5 9 想像自己是圖中的某點 v 身旁有一些鄰點 u u 知道源點到他們那裡的最小成本 v 知道 u 到自己那裡的成本 (邊權重) v 能計算各點到 v 的成本 v 就能得知，源點到 v 的最小成本 8 13 6 9

239 Relaxation 實作 int update = cost[u] + w; // w := weight cost[v] = min(cost[v], update);

240 Questions?

241 單源最短路徑 Relaxation Dijkstra's algorithm Bellman-Ford's algorithm

242 Dijkstra's algorithm

243 Dijkstra 實作 vector<node> E[maxn]; // 邊集合 : . /* 假設輸入完邊的資訊了 */

244 Dijkstra 實作 (初始化) memset(s, 0x3f, sizeof(s)); //初始為無限大 priority_queue<node> Q; Q.push({source, s[source] = 0});

245 Dijkstra 實作 while (!Q.empty()) { node u = Q.top(); Q.pop(); for (node v: E[u.id]) { int update = u.w + v.w; if (update < s[v.id]) Q.push({v.id, s[v.id] = update}); } }

246 1 8 3 4 6 1 5 8 3 7 s 2 4

247 ∞ 初始化 1 8 ∞ 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

248 ∞ 拜訪中 1 8 ∞ 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

249 ∞ 拜訪鄰點 1 8 ∞ 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

250 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

251 ∞ Relax! 1 8 5 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

252 ∞ 拜訪鄰點 1 8 5 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

253 ∞ Relax? 1 8 5 3 ∞ 4 ∞ 6 1 ∞ 5 ∞ 8 3 7 2 ∞ ∞ 4

254 ∞ Relax! 1 8 5 3 ∞ 4 ∞ 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

255 ∞ 拜訪完 1 8 5 3 ∞ 4 ∞ 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

256 ∞ Queue 1 8 5 3 ∞ 4 ∞ 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

257 ∞ 拜訪鄰點 1 8 5 3 ∞ 4 ∞ 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

258 ∞ Relax? 1 8 5 3 ∞ 4 ∞ 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

259 ∞ Relax! 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

260 ∞ 拜訪鄰點 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

261 ∞ Relax? 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

262 6 Relax! 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

263 6 拜訪鄰點 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

264 6 Relax? 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

265 6 No 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

266 6 拜訪完 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

267 關於 relaxation 5 這個拜訪完的節點 在未來有可能再被 relax 嗎?

268 6 拜訪完 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

269 6 拜訪鄰點 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

270 6 Relax? 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

271 6 No 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

272 6 拜訪鄰點 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

273 6 Relax? 1 8 5 3 ∞ 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

274 6 Relax! 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

275 6 拜訪完 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

276 6 關於 relaxation 5 這些拜訪完的節點 在未來有可能再被 relax 嗎?

277 6 關於 relaxation 5 這些拜訪完的節點 在未來有可能再被 relax 嗎? 若答案為否定的， 這似乎叫做: 無後效性

278 6 拜訪完 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

279 6 拜訪鄰點 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

280 6 拜訪鄰點 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

281 6 拜訪鄰點 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

282 6 Relax? 1 8 5 3 14 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

283 6 Relax! 1 8 5 3 12 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

284 6 拜訪完 1 8 5 3 12 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

285 6 拜訪鄰點 1 8 5 3 12 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

286 6 拜訪完 1 8 5 3 12 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

287 6 拜訪鄰點 1 8 5 3 12 4 8 6 1 8 5 ∞ 8 3 7 2 ∞ ∞ 4

288 6 Relax! 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 19 4

289 6 拜訪完 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 19 4

290 6 無後效性 5 12 若 u 去 relax 了 v 8 8

291 6 無後效性 5 12 若 u 去 relax 了 v 則未來不管如何， v 不可能更新 u 8 8

292 6 無後效性 5 12 若 u 去 relax 了 v 則未來不管如何， v 不可能更新 u 因為 u 先來的 8 8

293 6 無後效性 5 12 若 u 去 relax 了 v 則未來不管如何， v 不可能更新 u 因為 u 先來的，在 u 之後挑的任何點 其值都比 u 大，並且邊權重恆正 ! 怎麼加都比 u 大 8 8

294 6 拜訪鄰點 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 19 4

295 6 Relax? 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 19 4

296 6 Relax! 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 15 4

297 6 拜訪完 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 15 4

298 6 拜訪鄰點 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 15 4

299 6 拜訪完 1 8 5 3 12 4 8 6 1 8 5 13 8 3 7 2 15 15 4

300 S 到 T? 1 8 3 4 6 1 5 8 3 7 S 2 T 4

301 15 1 8 3 12 4 6 1 8 5 13 8 3 7 2 15 4

302 Questions?

303 練習 POJ 3255 Roadblocks

304 單源最短路徑 Relaxation Dijkstra's algorithm Bellman-Ford's algorithm

305 Bellman-Ford's algorithm

306 Bellman-Ford 實作 vector<edge> E; : /* 假設輸入完邊的資訊了 */

307 Bellman-Ford 實作 memset(s, 0x3f, sizeof(s)); // 初始無限大 s[source] = 0;

308 Bellman-Ford 實作 for (int i = 0; i < V.size(); i++) for (edge e: E) s[e.v] = min(s[e.v], s[e.u] + e.w);

309 1 8 3 4 2 5 8 s

310 ∞ 初始化 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

311 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

312 ∞ No 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

313 ∞ 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

314 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

315 ∞ No 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

316 ∞ 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

317 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

318 ∞ No 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

319 ∞ 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

320 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

321 ∞ No 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

322 ∞ 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

323 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

324 ∞ No 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

325 ∞ 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

326 ∞ Relax? 1 8 ∞ 3 ∞ 4 ∞ 2 ∞ 5 8

327 ∞ Relax! 1 8 5 3 ∞ 4 ∞ 2 ∞ 5 8

328 ∞ 1 8 5 3 ∞ 4 ∞ 2 ∞ 5 8

329 ∞ Relax? 1 8 5 3 ∞ 4 ∞ 2 ∞ 5 8

330 ∞ Relax! 1 8 5 3 ∞ 4 ∞ 2 8 5 8

331 ∞ 1 8 5 3 ∞ 4 ∞ 2 8 5 8

332 ∞ Relax? 1 8 5 3 ∞ 4 ∞ 2 8 5 8

333 ∞ No 1 8 5 3 ∞ 4 ∞ 2 8 5 8

334 ∞ 1 8 5 3 ∞ 4 ∞ 2 8 5 8

335 ∞ Relax? 1 8 5 3 ∞ 4 ∞ 2 8 5 8

336 6 Relax! 1 8 5 3 ∞ 4 ∞ 2 8 5 8

337 6 1 8 5 3 ∞ 4 ∞ 2 8 5 8

338 6 Relax? 1 8 5 3 ∞ 4 ∞ 2 8 5 8

339 6 Relax! 1 8 5 3 12 4 ∞ 2 8 5 8

340 6 1 8 5 3 12 4 ∞ 2 8 5 8

341 6 Relax? 1 8 5 3 12 4 ∞ 2 8 5 8

342 6 Relax! 1 8 5 3 12 4 ∞ 2 7 5 8

343 6 1 8 5 3 12 4 ∞ 2 7 5 8

344 6 Relax? 1 8 5 3 12 4 ∞ 2 7 5 8

345 6 Relax! 1 8 5 3 12 4 8 2 7 5 8

346 6 1 8 5 3 12 4 8 2 7 5 8

347 6 Relax? 1 8 5 3 12 4 8 2 7 5 8

348 6 No 1 8 5 3 12 4 8 2 7 5 8

349 6 1 8 5 3 12 4 8 2 7 5 8

350 6 Relax? 1 8 5 3 12 4 8 2 7 5 8

351 6 No 1 8 5 3 12 4 8 2 7 5 8

352 6 1 8 5 3 12 4 8 2 7 5 8

353 6 1 8 5 3 12 4 8 2 7 5 8

354 6 1 8 5 3 12 4 8 2 7 5 8

355 6 1 8 5 3 12 4 8 2 7 5 8

356 6 1 8 5 3 12 4 8 2 7 5 8

357 6 1 8 5 3 12 4 8 2 7 5 8

358 6 Relax! 1 8 5 3 11 4 8 2 7 5 8

359 6 1 8 5 3 11 4 8 2 7 5 8

360 6 1 8 5 3 11 4 8 2 7 5 8

361 6 1 8 5 3 11 4 8 2 7 5 8

362 6 1 8 5 3 11 4 8 2 7 5 8

363 6 1 8 5 3 11 4 8 2 7 5 8

364 6 1 8 5 3 11 4 8 2 7 5 8

365 6 1 8 5 3 11 4 8 2 7 5 8

366 6 1 8 5 3 11 4 8 2 7 5 8

367 6 1 8 5 3 11 4 8 2 7 5 8

368 6 結束了嗎? 1 8 5 3 11 4 8 2 7 5 8

369 結束了嗎? 結束了。

370 可是 要怎麼判斷，每個點都得到最短路了?

371 路就是一條直直的

372 所以 至多要做 |V| - 1 次的全部邊 relaxtion 剛剛的例子只做了 3 遍 自行證明吧

373 負權重邊 對每邊做至多 |V|−1 次 relaxation 後， 要是某邊還能 relaxation，

374 負權重邊 對每邊做至多 |V|−1 次 relaxation 後， 要是某邊還能 relaxation， 就表示有負權重邊能使路徑成本一直降低。

375 Questions?

376 練習 UVa OJ 558 Wormholes

377 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

378 A* search

379 評估函數 下一步到底該往哪走?

380 評估函數 下一步到底該往哪走? (透過轉移方程找可走鄰點)

381 評估函數 下一步到底該往哪走? 走下去，會更好嗎?

382 評估函數 下一步到底該往哪走? 走下去，會更好嗎? 好或不好，就是由評估函數決定 得自行設計

383 評估函數 g(n): 從起點到 n 點的成本 h(n): 從 n 點到終點的成本 f(n) = g(n) + h(n): 評估函數

384 例如 當求帶權重圖的單源最短路徑 g(n) = 從起點到 n 的最小成本 h(n) = 0 這個是， Dijkstra 演算法

385 例如 當求二維平面圖的單點到單點最短路徑 g(n) = 0 h(n) = n 點到終點的歐幾里得距離
這個是， Best-first search 演算法 不是 Breadth-first search

386 Outline 術語複習 Graph Tree 最小生成樹 A* 搜尋法則 單源最短路徑 全點對最短路徑

387 All-Pairs Shortest Paths

388 APSP 問任意點到任意點的最小成本

389 樸素解 利用剛才教的 SSSP 演算法們 對每個點都設定為源點 (source)

390 樸素解 利用剛才教的 SSSP 演算法們 對每個點都設定為源點 (source) 當然可以!

391 全點對最短路徑 Floyd-Warshall's Algorithm Johnson's Algorithm

392 全點對最短路徑 Floyd-Warshall's Algorithm Johnson's Algorithm

393 Floyd-Warshall's Algorithm

394 Floyd-Warshall 實作 int s[maxn][maxn]; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) s[i][j] = G[i][j]; for (int k = 1; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) s[i][j] = min(s[i][j], s[i][k] + s[k][j]);

395 狀態/轉移方程 設定狀態 𝑠 i,j,𝑘 為 𝑖 到 𝑗 只以 1,..,𝑘 為中間點的最小成本

396 狀態/轉移方程 設定狀態 𝑠 i,j,𝑘 為 𝑖 到 𝑗 只以 1,..,𝑘 為中間點的最小成本 𝑠 i,j,𝑘 = 𝑠 𝑖, 𝑗, 𝑘−1 若無經過 𝑘 s i,𝑘, 𝑘−1 +𝑠 𝑘, 𝑗, 𝑘−1 若有經過 𝑘

397 狀態/轉移方程 設定狀態 𝑠 i,j,𝑘 為 𝑖 到 𝑗 只以 1,..,𝑘 為中間點的最小成本 𝑠 i,j,𝑘 = 𝑠 𝑖, 𝑗, 𝑘−1 若無經過 𝑘 s i,𝑘, 𝑘−1 +𝑠 𝑘, 𝑗, 𝑘−1 若有經過 𝑘 𝑠 i,j,𝑘 =𝑚𝑖𝑛(𝑠 𝑖, 𝑗, 𝑘−1 , s I,𝑘, 𝑘−1 +𝑠 𝑘, 𝑗, 𝑘−1 )

398 邊界 𝑠 i,j,0 = 　　 若 𝑖=𝑗 𝑤𝑒𝑖𝑔ℎ𝑡 𝑖, 𝑗 　若有 𝑖, 𝑗 邊 ∞ 　 若無 𝑖, 𝑗 邊

399 全點對最短路徑 Floyd-Warshall's Algorithm Johnson's Algorithm

400 Johnson's Algorithm

401 Johnson's Algorithm 結合了 Bellman-ford 與 Dijkstra 的演算法 其複雜度為兩個演算法複雜度相加

402 Johnson's Algorithm 自行研究吧

403 Questions?