---
tags: 演算法
---
# 演算法 期末考 筆記
### 課本習題的解答多看有益身心健康
https://walkccc.me/CLRS/Chap24/24.3/
https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html
# ch12 Binary Search Trees

- INORDER_TREE_WALK(x)
- Θ(n)
- 補充：Inorder、Preorder、Postorder tree walk

- TREE_SEARCH(x, k)
- O(h)
- ITERATIVE_SEARCH(x, k)
- 例題12.2-1 哪個組合不可能是BST search 363的過程？
- 參考答案：c、e是錯的
- 例題12.2-4 Professor Bunyan發現一個屬性
search path左邊的所有節點a < search path上的所有的節點b < search path右邊的所有節點c
解釋是否正確？
- 參考答案：不正確 (以下範例假設要search key 4)

- TREE_MINIMUM(x)
- O(h)
- TREE_MAXIMUM(x)
- O(h)
- TREE_SUCCESSOR(x)
1. 如果x.right不是null，先找x右子樹的最小值TREE-MINIMUM(x.right) (ex.15的successor為17)

3. 如果x.right是null，往上找x的祖先y，直到找到第一個y的左子樹是x的祖先 (ex.13的successor為15)

- The dynamic-set operations：O(h)(tree of height h)
- 例題12.2-5 證明一個node有兩個小孩，則他的successor沒有左邊小孩，他的predecessor沒有右邊小孩
- 參考解答：
假設node x有兩個小孩
x的successor是x的right tree中最小的，不可能還有左邊小孩
x的predecessor是x的left tree中最大的，不可能還有右邊小孩

- Tree-Insert(T, z)
- O(h)
- Tree-Delete(T, z)
- O(h)
- Transplant(T, u, v)
- Replace the subtree of u with the subtree of v
- TREE_MINIMUM(x)

Deletion
1. z has no children
2. z has just one child
a. 若z.left = NIL，z.right取代z
b. 若z.right = NIL，z.left取代z
4. z has two children
**取y為Tree-Minimum(z.right)**
c. 若y.p=z，y取代z，z的左子樹變成y的左子樹
d. 若y.p!=z，先將y的右子樹取代y，再將y取代z，z的左子樹變成y的左子樹
(這裡要注意y是z的右子樹的最小值，不會有left，所以圖上y.left都畫NIL)

The dynamic-set operations：O(h)

# ch13 Red-Black Trees
- 13.1 Properties of red-black tree
- 在最壞的情況下花費O（log n）時間
- 紅黑樹是一種BST額外增加一個bit紀錄顏色(紅/黑)
- 透過顏色標記的限制方式，讓the root to a leaf的path不會超過其他path的兩倍，使BST大約平衡
- 符Red-Black Tree的條件(可能會考如何判斷是不是紅黑樹 ex.課本例題13.1-2)
1.每個點不是紅就是黑
2.root是黑色
3.所有leaf(NIL)是黑色
4.如果某個節點是紅色，那他的小孩一定是黑色
5.以某個節點為起點，往下到所有葉子的的路徑上的黑點數量相同
- Lemma13.1：A red-black tree with n internal nodes has height at most **2lg(n+1)**.
- 13.2 Rotations
- The code for RIGHT-ROTATE is symmetric.
- Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time.

- 可能會考如何畫rotation前後如何畫圖(ex.如下圖)

- 13.3 Insertion
- O(lg n)
- Insert Node的方法和Binary Search Tree大致相同相同，假設insert Node z，最後要分別做以下動作讓樹的結構還是一個RB-Tree
- z.left=NIL
- z.right=NIL
- z.color=Red
- RB-INSERT-FIXUP(T, z)
- RB-INSERT-FIXUP(T, z)
- Insert後如果z的parent是Red時
1. 如果z的parent是z的爺爺的左邊小孩(z.p=z.p.p.left)，有三種情況與處理方式
**Case 1: z’s uncle y is red**
ToDo：將z的parent和z的uncle顏色換成black，把z的爺爺換成red，z變成的爺爺(z=z.p.p)，如圖a到圖b的過程
**Case 2: z’s uncle y is black and z is a right child**
ToDo：z變成z的parent(z=z.p)，進行LEFT-ROTATE(T, z)，如圖b到圖c的過程
**Case 3: z’s uncle y is black and z is a left child**
ToDo：將z的parent變成黑色，將z的爺爺變成紅色，再進行RIGHT-ROTATE(T, z.p.p)，如圖c到圖d的過程
**重要：最後要把root圖黑(無論如何root一定要是黑色!!!)**
2. 如果z的parent是z的爺爺的右邊小孩(z.p=z.p.p.right)的三種情況與處理方式，只要把上面情況的left/right互換即可
- 要隨時注意z和y的位置變化比較好理解
- 例題13.3-2 Show the red-black trees that result after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree.
- 參考答案：

- 13.4 Deletion
- O(lg n)
- RB-DELETE(T,z)
- 如果被刪除的節點是紅色 => RB tree的平衡還在
- **如果被刪除的節點是黑色 =>會違反RB Tree的原則，要執行RB-DELETE-FIXUP**
- RB-DELETE-FIXUP(T, x)
-如果x不是root && x是黑色
- 觀念：不管x點是紅還是黑，y少掉的黑帶在x身上 => 只要是x都多帶一個黑
1. 如果x是x的parent的左邊小孩(x=x.p.left)，有四種情況與處理方式
**Case 1: x’s sibling w is red**
ToDo：w塗黑，x的parent塗紅，LEFT-ROTATE(T, x.p)，new w為x.p.right，如圖a
**Case 2: x’s sibling w is black, and both of w’s children are black**
ToDo：w塗紅，new x為x.p，如圖b
**Case 3: x’s sibling w is black, w’s left child is red, and w’s right child is black**
ToDo：w塗紅，w.left塗黑，RIGHT-ROTATE(T,w)，new w為x.p.right，如圖c
**Case 4: x’s sibling w is black, and w’s right child is red**
ToDo：w塗x的parent的顏色，x的parent塗黑，LEFT-ROTATE.T(x,p)，new x為T.root，如圖d
**重要：最後要把x(root)塗黑(無論如何root一定要是黑色!!!)**
2. 如果x是x的parent的右邊小孩(x=x.p.right)，有四種情況與處理方式，只要把上面情況的left/right互換即可
- 要隨時注意x和w的位置變化比較好理解
- 例題13.4-3 依照13.3-2的結果依序刪除8; 12; 19; 31; 38; 41.
- 參考答案：

# ch18 B-Trees
- B-Tree特性
- 每一棵B-Tree都需要在建立前指定好minimum degree ≧ t 。
- 樹上的每個節點內存放最少t-1個keys，最多2t-1個Keys。
- Root Node較為特殊，允許存放最少1個Key，最多2t-1個Keys。**如果Node已經有2t-1個keys稱為full。**
- 若節點有n個keys，則有n+1個小孩
- 每個節點上的Keys都是以升序排列，相隔的兩Key，K1、K2，之間的任一子節點上的任一Key，其值必落在 K1~K2 之間。
- 所有葉節點（Leaf Node）的深度（Depth）必定相同(= tree's height h)。

- Search
- Run Time 
- B-Tree 的 Search 從 Root Node 開始，比對目標 Key 與所在節點上的 Key 的值。若目標 Key 的值：
1. 小於最小Key，就往節點上最左方的子節點往下移動。
2. 落在某二鄰近 Key 之間，就往此二鄰近 Key 之間的子節點往下移動。
3. 大於最大Key，就往節點上最右方的子節點往下移動。
- 重複直到找到相符或找到葉節點還找不到為止。
- Creating an empty B-tree
- O(1)
- Insert　（從上往下跑，遇到滿的就炸開）（滿：2t-1）
- Run Time 
- 從root沿路scan，**只要遇到full就先split**
- t=3為例，Insert B、Q、L、F

- Delete　（從上往下跑，遇到不足的就合起來）（不足：t-1）
- Run Time 
- 從root沿路掃到下面delete key的處理方式：
- Case1：如果key所在的節點是葉子，直接delete，如圖b
- Case2：如果key所在的節點為 Internal Node
a.如果key左邊指標指到的小孩數量為t，將小孩最大值(Predecessor)取代key的位置，如圖c
b.如果key右邊指標指到的小孩數量為t，將小孩最小值(Successor)取代key的位置
c.如果兩邊指標指到的小孩數量都不足t，將key和兩個小孩合併後delete key，如圖d
- Case3：key經過的Node稱為x.c，如果x.c只有t-1個Key，要先將x.c補滿到t個key
a.如果x.c左邊兄弟有t個key，將x.c parent key給x.c，將左邊兄弟最右邊key給x.c parent，左邊兄弟的右邊小孩給x.c。如果x.c右邊兄弟有t個key，將x.c parent key給x.c，將右邊兄弟最左邊key給x.c parent，右邊兄弟的左邊小孩給x.c。如圖f
b.如果兩邊兄弟都只有t-1個key，將x.c與左邊兄弟(或右邊兄弟)與他們中間的parent key做合併，處理好後在往下走進行delete key，如圖e

- t=3為例，Delete F、M、G、D、B

# ch19 Fibonacci Heaps
- Structure of Fibonacci heaps
- 上層為root list，root list最小的點為H.min
- 曾經失去一個小孩就會變成黑色(H.mark=true)
- 變成別人小孩就會變成白色(H.mark=false)
- Potential function
-  = number of trees + 2 * number of marks
- Maximum degree
- D(n) = O(lg n) → 任何人的小孩個數頂多lgn個

- Creating a new Fibonacci heap
- O(1)
- Make-Fib-Heap()

- Inserting a node
- O(1)
- Fib-Heap-Insert(H, x)
- 將key insert到root list，通常放在H.min的左邊，如果新增的key比較小就指定為H.min，以下為insert key 21的範例

- Finding the minimum node (找最小值)
- O(1)
- Minimum(H)
- 最小值在H.min

- Uniting two Fibonacci heaps (將H1、H2合併)
- O(1)
- Fib-Heap-Union(H1, H2)
- 將H1、H2的root list連在一起，再比較H1.min和H2.min誰比較小，指定為新的Heap的H.min

- Extracting the minimum node(取出最小值)
- O(D(n)) = O(lg n)
- Fib-Heap-Extract-Min(H)
- z=H.min，將z的兒子都放到root list，取出z，並指定z的右邊root為新的H.min，如圖b
- 從H.min往右使用一個陣列紀錄degree，若遇到將相同degree的root就做合併，小的當root，一直到沒有相同degree的root，如圖c到l
- 將root list最小值指定為H.min，如圖m

- Decreasing a key (把某個key的值變小)
- O(1)
- Fib-Heap-Decrease-Key(H, x, k)
- 用途：將key變小，就可以用Extracting the minimum node方法將key刪除
- 步驟： ***每人最多失去一個孩子，若超過，移到root list**
1. 將key值變小後放到root，如果key原本的parent為白色(H.mark=false)，則塗成黑色，如圖b、c
2. 如果放到root的key原本的parent是黑色(H.mark=true)，也要放到root，如圖d
3. 重新指定H.min
- 以下舉例46→15和35→5

- Deleting a node
- O(D(n)) = O(lg n)
- FIB-HEAP-DELETE(H, x)
- 將要刪除的key值變成負無限大 → FIB-HEAP-DECREASE-KEY(H,x,-∞)
- 取出最小值後刪除 → FIB-HEAP-EXTRACT-MIN(H)

# ch21 Data Structures for Disjoint Sets
- Disjoint Sets：「互斥集」的意思是一堆集合們，大家擁有的元素都不相同，也就是說**這些集合們之間都沒有交集**。
- ex. A = {1,2,3} B={4,5,6} C={1,2,7}，則AB構成Disjoint Sets，AC不構成Disjoint Sets。
- Disjoint Set的操作：
- MAKE-SET(x)：MAKE 建立一個只含x的set。因為互斥，所以x不能在其他集合出現過。
- UNION(x,y)：Union 是將兩個含有x和y的集合合併。
- FIND-SET(x)：Find 則是查詢某個元素所在的集合。
- 參數定義：
- m：總共有m個opterations(make、union、find)
- n：其中包含n個make operations
- CONNECTED-COMPONENTS：一開始將每個點單獨看成不同的集合，對於每一條edge(u,v)，假設u,v在不同的集合之內，就將包含他們的集合聯集起來，最後看剩下幾個集合，就是有幾個connected component。

- 例題21.1-1
- 參考答案：

- Linked List v.s. rooted tree
| | linked List | rooted tree |
| -------- | ----------- | ----------- |
| make | O(1) | O(1) |
| union | O(n^2) 費時 | O(α(n)) 快 |
| find | O(1) 快 |O(mα(n)) 慢→快|
- α(n)是Ackermann’s function的反函數，其成長速率非常慢。在所有可能的應用中，α(n) <= 4 (近乎常數頂多是4)
- rooted tree的find function本來很慢改善後可以變快→O(mα(n)) worst case

- Linked-list representation of disjoint sets
- A simple implementation of union(不考慮每個set的長度)
- 以序列中第一個元素當作代表人(representative)。
- A weighted-union heuristic(考慮每個set的長度，短的併到長的)
- 每一個representative存放其代表的序列的長度。
- 把較短的序列附加在較長的序列之後。(可以節省union時間)

- Disjoint-set forests (rooted tree)
- Tree的root為代表人(representative)。
- 改善running time的方法：
- **Union by rank**: 由較小高度的的tree的root連到較大的tree的root。
- **Path compression**: 在執行Find-Set(x)過程中，把所有經過的node都掛在root底下。 (壓縮)

# ch22 Elementary Graph Algorithms (初級圖演算法)
## 22.1 Representations of graphs(圖形表示)
1. 無方向(Undirected graph: no orientation is specified)
2. 有方向(Directed graphs: Oriented, the adjency matrix is not necessarily symmetric)
3. 矩陣 [adjacency-matrix representation (dense)]
4. 串列 [adjacency-list representation (sparse)]
- 無方向：矩陣&串列表示法
- 有方向：矩陣&串列表示法
## 22.2 Breadth-first Search (BFS:廣度優先)
- BFS(G,s)：圖形G中，計算*s*到其他點的最短距離
- Analysis Complexity:O(V+E)
- 應用：**Queue(先進先出)**；ENQUEUE(Q,s)：s放入Queue中；DNQUEUE(Q)：Queue中取值
- 屬性
- color：顏色註記[白色（未搜尋過），灰色（已搜尋過，丟Queue中）和黑色（搜尋完成，沒有相鄰點，移出Queue）]
- d：距離(distance )
- π：前一個節點
- adj[u]：*u*點相鄰的點集合

- line:1-8，初始化
- line:1-4，*s*外的點給予初值
- line:5-7，*s*點給予初值
- line:8，Queue給予初值
- line:9，起點s放入Queue中，透過Queue的特性完成廣度優先搜尋
- line:10，持續執行到Queue為空為止 (loop level1)
- line:11，取出Queue的值為*u*
- line:12，將*u*相鄰的點依序取出為*v* (loop level2)
- line:13-17，若*v*顏色為白色者(未搜尋過)則註記為灰色，將該點*v*的距離(*d*)紀錄為*u*的距離加1，並留下v的前一個節點(*π*)為*u*後放入放入Queue中
- line:18，將u標記為黑色視為以搜尋完成所有相鄰的點


> 參考網址：Graph: Breadth-First Search(BFS，廣度優先搜尋)
> http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html

- Shortest paths：當我們用BFS找端點對端點最短路時，從出發點開始，第一次遍歷到終點時過的那條路徑就是最短的路徑。

## 22.3 Depth-First Search (DFS:深度優先)
- Complexity:O(V+E)
- 應用：**Recursion**的方式做深度優先持續往下鑽
- 屬性
- color：顏色註記[白色（未拜訪過），灰色（已拜訪過，可拜訪相鄰的點）和黑色（拜訪完成，沒有相鄰點可拜訪）]
- d：發現(discovered)
- f：完成(finished)
- π：前一個節點
- adj[u]：*u*點相鄰的點集合

- line:1-3，loop所有點初始化
- line:4，time初值
- line:5-7，loop所有點*u*，判斷白色(未拜訪過)的點後執行[DFS-VIST(G,u) Recursion]recurse

- line:1-3，透過time累計拜訪次數，並將目前次數賦予目前拜訪的點 *u.d* 後將該點顏色註記為灰色
- line:4-7，loop所有*u*相鄰的點*v*，判斷白色(未拜訪過)的點，紀錄前一個節點(*π*)為*u*後執行[DFS-VIST(G,v) Recursion]recurse
- Classification of edges:
1. Tree edges：2-4以外的邊。
2. Back edges(B)：經過的邊拜訪到的點為灰色時。
3. Forward edges(F)：經過的邊拜訪到的點為黑色時。
4. Corss edges(C)：不同component的edge。
- 
> 參考網址：Graph: Depth-First Search(DFS，深度優先搜尋)
> http://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html

## 22.4 Topological Sort (拓撲排序)
- 有方向無循環(directed acyclic graph)
- 正確的Topological Sort可能不止一種

- 透過DFS(G)計算各節點完成時間(標記黑色的順序)
- 將各節點完成時間由大到小排序

- 做DFS下鑽到最後一個點時，因沒有相鄰的而返回表示無循環；反之，有相鄰的點但皆為灰色點而返回表示有循環
> 參考網址：Graph: 利用DFS尋找DAG的Topological Sort(拓撲排序)
> http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-dagde-topological-sorttuo-pu-pai-xu.html
## 22.5 Strongly connected components (強關聯元件)
- 有向圖
- Complexity:O(V+E)

- 透過DFS(G)計算各節點完成時間(*u.f*：標記黑色)[如下圖(a)]
- 將圖的所有方向顛倒產生G^T^(Transpose of Graph)[如下圖(b)]
- 透過DFS(G^T^)計算，DFS主程式的loop按line:1的完成時間(*u.f*)遞減順序執行
- line:3運行DFS主程式的loop每判斷為白色(未拜訪過)做recurse為一個component(each tree in the depth-first forest)

- component graph一定是directed acyclic graph(DAG)。

> 參考網址：Graph: 利用DFS尋找Strongly Connected Component(SCC)
> http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-strongly-connected-componentscc.html

# ch23 Minimum Spanning Trees (MST，最小生成樹)
- 從圖中找出最小生成樹(MST)的問題
- 無向圖(undirected graph)，端點都有連接(connected)且有權重(weight)的圖，希望找出沒有循環並能連接所有點的子集合，且總權重要是最小的。
- Spanning Tree：沒有循環且連結所有點
## 23.1 Growing a minimum spanning tree
- line:1，A為邊的空集合，初始化
- line:2-4，A集合還未形成spanning tree下，持續loop找出一個對A集合是**安全**(**safe**)的邊(edge)後，聯集(union)到A集合中。
- **安全**(**safe**)定義：區分點(vertex)的集合和邊(edge)的集合，演算法中為邊(edge)的集合，而以下定義有部分在說點的集合。
- 名詞解釋：
- cut(切割)：點(vertex)集合，分成兩部分的partition(分割)，spanning tree用的點集合
- crosses(交叉)：邊(edge)集合，一個邊(edge)串連cut的partition與圖其他點的邊，稱為crossing edge
- respects(尊敬)：Set A中沒有任何一條edge是crossing edge
- light edge(輕量邊)：crossing edge中權重(weight)最小的邊
- 定理1：符合四點表示**安全**(**safe**)
1. 圖要相連、有權重且無方向的圖
2. 集合A是MST的子集合
3. 集合A要有respects
4. line:3找的邊要為crossing edge且要是light edge
- 推論2：如下集合A的connected component也符合**安全**(**safe**)
1. 同定理1,2點的情境
2. 集合A中的數個connected component皆可視為一棵樹
3. 連結各個connected component的light edge(同定理4)

> 參考網址：Minimum Spanning Tree：Intro(簡介)
> http://alrightchiu.github.io/SecondRound/minimum-spanning-treeintrojian-jie.html

- Kruskal and Prim summary
- Kruskal’s algorithm：所有邊找權重由小到大完成MST
- Prim’s algorithm：從一個起始點開始往外找每個點相鄰的最小權重的邊

## 23.2 Algorithms of Kruskal and Prim
### Kruskal’s algorithm
- line:1-3，初始化
- line:4，把圖的所有邊(edges)以權重(weight)由小到大做排序
- line:5-8，loop所有邊(edges)依權重由小到大運行，判斷邊 *u* 和 *v* 在不同集合中，便將邊(u,v)放入A集合中，*u* 和 *v* 的點集合聯集

> 參考網址：Minimum Spanning Tree：Kruskal's Algorithm
> http://alrightchiu.github.io/SecondRound/minimum-spanning-treekruskals-algorithm.html

### Prim’s algorithm
- line:1-4，初始化
- line:5，所有點丟入a min-priority queue Q based on a key attribute
- line:6-7，Queue中取出最小的做為 *u* 至Queue取空為止 (loop level 1)
- line:8-11，所有 *u* 的相鄰的點依序取出為 *v* (loop level 2)，判斷 *v* 點仍存在於Queue中，且 *u* 到 *v* 之間的權重找最小者

> 參考網址：Minimum Spanning Tree：Prim's Algorithm
> http://alrightchiu.github.io/SecondRound/minimum-spanning-treeprims-algorithm.html

# ch24 Single-Source Shortest Paths
- shortest-path weight δ(u,v) from u to v
- v.d = d[v]指的是目前到v點的距離
v.π指的是v的前一個點(predecessor)

- single-source shortest-paths problem與他的三種變形 (Variants)
1. single-source shortest-paths problem
從單一vertex，抵達Graph中其餘所有vertex之最短路徑。(一對多)
2. Single-destination shortest paths problem
從Graph中的每一個vertex抵達某個特定vertex之最短路徑，剛好與第1種問題的子問題相反。(多對一)
3. Single pair shortest path problem
從單一vertex，抵達某個特定vertex之最短路徑，此為第1種問題的子問題。(一對一)
4. All-pair shortest paths problem
Graph中的所有vertex抵達其餘所有vertex之最短路徑。(多對多)
- 若把每一個vertex都當作起點，即可利用第1種問題之方法解決。
- 不過Ch25介紹的**Floyd-Warshall Algorithm**有更好的答案。
- Optimal substructure of a shortest path
- Optimal substructure定義：原問題的最佳解是由其子問題得的最佳解算出來的
- Lemma 24.1. Subpaths of shortest paths are shortest paths(最短路徑中的子路徑也都是最短路徑)

- 順帶一提：最長路徑不為Optimal substructure
- Negative-weight edge/cycle
- 最短路徑的weight可正可負，但不能包含負的cycles(Negative cycles)，因為一直繞會變-∞
ex.下圖的ef和hij，都造成Negative cycles使結果變成-∞

- Shortest paths are not necessarily unique, and neither are shortest-paths trees
Shortest paths可以有多組解，如下圖b和c陰影路徑都呈現了最短路徑的解，都以s為起點但結構不同的shortest-paths trees

- Relaxation 鬆弛
考慮是否使用u→v這條線edge(u,v)會比較好？
如果v.d > u.d + w(u,v)，則可以走edge(u,v)
此時紀錄v.d的值為u.d + w(u,v)，v.π = u
time complexity= O(1)

- Properties of relaxation (不想看就跳過)

- The Bellman-Ford algorithm 貝爾曼-福特演算法
- Time complexity O(VE)
- 權重可以是負的，但不能有負的cycle
- 參考課本圖解
- 依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑

- 或者參考網址：http://alrightchiu.github.io/SecondRound/single-source-shortest-pathbellman-ford-algorithm.html
hint：
predecessor代表個點的前一個點，
distance代表目前為止這個點計算出來的最短路徑距離
一開始所有點的predecessor都設定為-1，所有點的distance都設定為∞
接著依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑

- Single-source shortest paths in directed acyclic graphs(有向無環圖)
- Time complexity O(V+E)
- 先把topological sort做完，再沿路relax
- 補充：
之前說過shortest path是簡單的題目，longest path是難的題目，但是如果是directed acyclic graphs(有向無環圖)，則longest是簡單的題目。

- Dijkstra’s algorithm 戴克斯特拉演算法
- Time complexity O(V^2) (使用BFS方法)

- 權重不能有負號
- 模擬BFS方法沿路relax，但途如果有多個點可以走，EXTRACT_MIN(Q)取值最小的點繼續往下走，如圖b(5比10小)，如圖c(7比8和14小)，以此類推，直到所有點都已經塗黑
- EXTRACT_MIN(Q)即是採用Greedy strategy

# ch25 All-Pairs Shortest Paths
## 25.1 Shortest paths and matrix multiplication
- dynamic-programming algorithm
- Initial
- Then
- Time Complexity O(n^4)
- 改善running time => using repeated squaring (例如W^4 寫成 W^2 * W^2，減少計算次數) => Time Complexity 


## 25.2 The Floyd-Warshall algorithm
- Time complexity O(N^3)
- 從vertex(i)走到vertex(j)，逐一引入中繼點vertex(k)
 為「已將集合K{1,2,3,...k}中的所有vertex作為中繼點引入集合S」後，從起點vertex(i)走到終點vertex(j)的路徑之成本。

- 參考課本圖解：計算每一個點i到其他點j的距離(ex. 看i=1那行，1到2的距離為3，1到3的距離為8，1到4的距離為∞...)
- 或者參考網址內的圖解：http://alrightchiu.github.io/SecondRound/all-pairs-shortest-pathfloyd-warshall-algorithm.html#floyd
- Initial
- 原本C→B，d=∞。引入A當中繼點，變成C→A→B，d=6
- 原本A→C，d=6。引入B當中繼點，變成A→B→C，d=0
- 原本A→D，d=9。引入B當中繼點，變成A→B→D，d=5
- 依此類推...
### Transitive closure of a directed graph (傳遞閉包)


# ch26 Maximum Flow
## 26.1 Flow networks
Flow networks and flows

## 26.2 The Ford-Fulkerson method (福特福克森方法)
計算網絡流的最大流的貪心算法。 之所以稱之為「方法」而不是「算法」，是因為它尋找增廣路徑的方式並不是完全確定的，而是有幾種不同時間複雜度的實現方式。

FORD-FULKERSON-METHOD(G,s,t)

三個重要應用：
1. Residual networks (剩餘網路)
2. Augmenting paths
3. Cuts

### Residual networks (剩餘網路)
residual capacity (剩餘容量)
### Augmenting paths
### Cuts

S在左；T在右，中間切一刀

> Corollary 26.5
> The value of **any flow** f in a flow network G is bounded from above by the capacity of **any cut** of G.
> 流量網絡G中任何流量f的值都由G的任意割斷的能力從上方限制。

> Theorem 26.6 (Max-flow min-cut theorem)

### The basic Ford-Fulkerson algorithm
FORD-FULKERSON(G,s,t)
running time:O(E|f*|)

## 26.3 Maximum bipartite matching
最多的配對

---

| ch | algorithm | Complexity |
| -------- | -------- | -------- |
| ch12 | Binary Search Trees | O(h) |
| ch13 | Red-Black Trees | O（log n） |
| ch18 | B-Trees | O(th)=O(t log~t~n) |
| ch19 | Fibonacci Heaps | O(lg n) |
| ch21 | Data Structures for Disjoint Sets | O(mα(n)) |
| ch22 | Elementary Graph Algorithms | O(V+E) |