# 演算法期末整理
## Greedy
### 背包
Input: 背包的最大容量m，以及可以放入背包的n個物品的非負重量wi與價格pi
Output: 介於0與1之間的x1,…,xn分別代表第1個,…,第n個物品放入背包中的零碎部份。可以最大化ΣPiXi，並且滿足ΣWiXi <= m
> Step 1: Sort pi/wi into non-increasing order.
> Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible.
```
時間複雜度
Step1: O(nlogn)
Step2: O(n)
total: O(nlogn)
```
### 01背包
x只能是0或1
### Huffman編碼
Input: 字元集合C與每個字元的出現頻率f
Output: Huffman編碼樹
```cpp=
n <- |C| //C: the set of n characters
Q <- C //Q: 優先佇列，以字元頻率為優先次序
for i 1 to n – 1
配置一個新的樹節點u
u.left <- GetMin(Q)
u.right <- GetMin(Q)
u.f <- x.f + y.f
Insert u into Q
return GetMIN(Q) 作為Huffman編碼樹的樹根
```
```
時間複雜度
建立priority_queue Q: O(n)
for中每次queue操作均為O(logn): O(nlogn)
total: O(nlogn)
```
### Kruskal algorithm(MST)
Input: 無向加權圖G=(V, E)，其中|V|=n
Output: G的最小含括樹(MST)H=(V, T)
```cpp=
T←empty //T為MST的邊集合，一開始設為空集合
while |T| < n-1 do
選出權重最小的邊(u, v)
E ← E - (u, v)
if ( (u, v)加入T中形成循環(cycle)(使用集合判斷) ) then 將(u, v)丟棄
else T ← T(u, v)
return H=(V, T)
```
```
時間複雜度
排序邊: O(|E|log|E|)
while中每次找出點所在的集合O(log|V|)聯集O(log|V|): O(|E|log|V|)
total: O(|E|log|V|) => since |E| < |V|^2 => O(｜V|^2log|V|) = O(n^2logn)
```
### Prim algorithm(MST)
Input: G=(V, E)為無向加權圖，其中|V|=n
Output：G的最小含括樹(MST)H=(V, T)
```cpp=
T←empty
X←{v} //隨意選擇一個節點v加入集合X中
while |T| < n-1 do
選出(u, v)，其中u<X且v<V-X，且(u, v)的加權(weight)最小
T←T+(u, v) //(u, v)是一個邊
X←X+{v}
return H=(V, T)
```
```
時間複雜度
while: O(n)
選出邊: O(n)
total: O(n^2)
O(ElngV) for using priority_queue
O(E+VlogV) for using fibonacci heap
so while E is very large prim is better
```
### Dijkstra(shortest path)
Input：給定一個非負加權有向圖(non-negative weighted digraph)G=(V, E)，及一個來源(source)節點s。G各邊的加權值以w[x][y]表示，其中x 及y為邊的二個節點。
Output：對每一個節點u而言，傳回一個由s到u的最短路徑距離(累積邊加權)d[u]。
```cpp=
d[s]←0; d[u]←∞ for each u≠s
將每一個節點加入優先佇列Q
while Q≠ do
自Q中移出具有最小d[u]值之節點u
for 每一個與u相鄰之節點x do
if d[x] > d[u]+w[u][x] then
d[x]←d[u]+w[u][x]
return d
```
```
時間複雜度
while: O(|V|)
extract min: O(log|V|)
for: O(|E|)
update: O(log|V|)
total: O( |V|+|E| log|V| )
```
## DP
### 最長共同子序列
> 轉移方程
> c[i, j] = 0, if i=0 or j=0
> c[i, j] = c[i-1, j-1] + 1, if i,j>0 and Xi=Yj
> c[i, j] = max(c[i, j-1], c[i-1], j), if i,j>0 and Xi!=Yi
Input: 兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn>
Output: X和Y的最長共同子序列長度
```cpp=
m <- length[X]
n <- length[Y]
for i <- 1 to m:
c[i, 0] <- 0
for j <- 1 to n:
c[0, j] <- 0
for i <- 1 to m:
for j <- 1 to n:
if Xi = Yj:
c[i, j] <- c[i-1, j-1] + 1
b[i, j] <- 3 // 3 for top left (i-1, j-1)
else if c[i-1, j] >= c[i, j-1]:
c[i, j] <- c[i-1, j]
b[i, j] <- 1 // 1 for top (i-1)
else
c[i, j] <- c[i, j-1]
b[i, j] <- 2 // 2 for left (j-1)
return c and b
PRINT_LCS(b, X, i, j):
if i = 0 or j = 0:
return
if b[i, j] == 3:
PRINT_LCS(b, X, i-1, j-1)
print(Xi)
else if b[i, j] == 1:
PRINT_LCS(b, X, i-1, j)
else
PRINT_LCS(b, X, i, j-1)
CALL PRINT_LCS(b, X, length[X], length[Y])
```
```
時間複雜度: O(m*n)
```
### 最大連續子序列和
Input: 包含n個正或負整數的序列S
Output: 最大連續非空子序列和
```cpp=
if 所有整數均為負數:
return max(S)
MCSS = m = s[1]
for i <- 2 to n:
m <- max(m+s[i], s[i])
MCSS <- max(MCSS, m)
return MCSS
```
### 最大連續可空子序列和
Input: 包含n個正或負整數的序列S
Output: 最大連續可空子序列和
```cpp=
if 所有整數均為負數:
return 0
MCSS = m = s[1]
for i <- 2 to n:
m <- max(m+s[i], s[i])
MCSS <- max(MCSS, m)
return MCSS
```
```
時間複雜度: O(n)
```
### 最小編輯成本
給定字串A=a1a2…am及字串B=b1b2...bn, MEC問題是要找到成本最低的一連串的編輯操作將字串A轉為字串B。可以使用的操作及其成本如下所述:
* 操作1: 由字串A刪除一個字元 (Cost1)
* 操作2: 在字串A插入一個字元 (Cost2)
* 操作3: 在字串A將一個字元換成另一個字元 (Cost3)
> 轉移方程
> c[i, j]表從A轉為B所需要的cost
>
> inital:
> c[i, 0] = i x Cost1
> c[0, j] = j x Cost2
>
> c[i, j] = c[i-1, j-1] if Ai = Bi
> C[i, j] = min(c[i-1, j]+Cost1, c[i, j-1]+Cost2, c[i-1, j-1]+Cost3) else
### 01背包
```cpp=
cin >> n;
for(int i=0 ; i<5 ; i++) cin >> input[i].weight;
for(int i=0 ; i<5 ; i++) cin >> input[i].value;
memset(dp, 0, sizeof(dp));
for(int i=0 ; i<5 ; i++)
for(int j=n ; j>=input[i].weight ; j--)
dp[j] = max(dp[j], dp[j-input[i].weight] + input[i].value);
cout << dp[n] << "\n";
```
### 多項式、偽多項式時間
> 對於“多項式時間”，我們的直觀概念是時間複雜度O(n^k ),其中k是一常數。比如，選擇排序的時間複雜度是O(n^2 )，是多項式時間；暴力解決TSP問題的時間複雜度是O(n*n!)，不是多項式時間。我們稱這種時間複雜度為“傳統時間複雜度”。'
>
我們通常認為傳統時間複雜度中的變量表示數據的輸入規模。比如，選擇排序中，指待排序數組中元素的個數；TSP問題中表示圖中節點的數量。但是，這些所謂的輸入規模，僅僅是直觀的定義，並不足夠嚴謹。為了標準化這些，在計算標準時間複雜度時，我們給出了輸入規模的標准定義：
**一個問題的輸入規模是保存輸入數據所需要的bit位數**
比如，如果排序算法的輸入是一個32-bit整數數組，那麼輸入規模就是32n，n是指數組中元素的個數。
了解了輸入規模的定義，我們來看“多項式時間”的標准定義：
**對於一個問題，在輸入規模為x的情況下，如果一個算法能夠在O( x^k )時間內解決此問題，則我們稱此算法是多項式時間的，其中k為一常數。**
當我們處理一些圖論、鍊錶、數組、樹等問題時，這個標准定義下的多項式時間和我們傳統的多項式時間相差無幾。
然而，當我們處理一些與數論有關的問題時，事情就不太樂觀了。現在我們來討論判斷一個整數是否為素數的算法，下面是一個簡單的算法：
```cpp=
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
```
顯然，這個算法在傳統時間複雜度計算方法中是多項式時間的。我們不妨認為它的傳統時間複雜度是O(n^4)。然後我們再來分析這個問題的輸入規模，可能有的同學會說，對於32-bit整數，這個輸入規模不就是32嗎？這話雖然沒錯，但是因為在這個問題中，輸入規模完全依賴於的大小，所以的範圍不再限制在32-bit整數的範圍內，而是要探討當更大時對數據規模的影響。我們知道，保存一個整數所需要的bit位數 x=logn，因此，在標準的時間複雜度中，此算法的複雜度變為了O(2^4x)這已經不再是多項式時間，而是一個指數時間。
偽多項式時間的定義：
**如果一個算法的傳統時間複雜度是多項式時間的，而標準時間複雜度不是多項式時間的，則我們稱這個算法是偽多項式時間的。**
### 子集合加總
思路與01背包很像
Input: 包含n個數值的集合S及一特定數值c
Output: True or False, 分別代表存在或不存在元素加總值為c的子集合
> dp[w]表集合S中加總最大但不超過w的數值，因此若dp[c] = c則可驗證存在
```cpp=
cin >> n >> c;
for(int i=0 ; i<5 ; i++) cin >> input[i];
memset(dp, 0, sizeof(dp));
for(int i=0 ; i<5 ; i++)
for(int j=c ; j>=input[i] ; j--)
dp[j] = max(dp[j], dp[j-input[i]] + input[i]);
if(dp[c] == c)
cout << "true";
else
cout << "false";
```
### 多階圖最小成本路徑
Input:具n個頂點(vertices)的k階多階圖G(V, E)
Output: path[1..k], d[s]，其中path[1..k]紀錄第1階(節點1)到第k階(節點n)的最小成本路徑，d[s]紀錄最小成本路徑總成本
```cpp=
d[t]=0; d[x]=INF for x != t
for i <- k-1 to 1:
for every node x in Pi:
for every edge (x, y):
if (d[x] < w[x, y] + d[y])
d[x] = w[x, y] + d[y]
next[x] = y
path[1] = s
path[k] = t
for j<-2 to k-1:
path[j] = next[path[j-1]]
return path, d[s]
```
```
時間複雜度: O(n^2)
```
### Bellman-Ford Algorithm
Input: 給定一加權有向圖 G=(V, E)，及一個來源節點s，G各邊加權值以w[x][y]表示
Output: 對於每一個頂點u，傳回一個由s到u的最短路徑d[u]
```cpp=
d[s]=0; d[u]=INF for each u != s
for i <- 1 to |V|-1:
for every edge in G (u, x):
if d[x] > d[u] + w[u][x]:
d[x] = d[u] + w[u][x]
for every edge in G (u, x):
if d[x] > d[u] + w[u][x]:
return false
return d
```
```
時間複雜度: O(|V|*|E|)
```
### Floyd-Warshall
Input: 給定一加權有向圖 G=(V, E)，及一個來源節點s，G各邊加權值以w[x][y]表示
Output: G中每一個節點配對的最短距離d[x][y]，及對應的路徑前節點p[x][y]
> pr[X][Y]=Z的物理意義是，從vertex(X)走到vertex(Y)的最短路徑上，vertex(Y)的predecessor為vertex(Z)
> 也就是說，vertex(Y)是透過edge(Z,Y)才接上Path:X−...−Z。
```cpp=
d[i][j]<-w[i][j] for each i and j
P[i][j]<-i for each i and j
for k <- 1 to n:
for i <- 1 to n:
for j <- 1 to n:
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j]
P[i][j] = P[k][j]
return d, P
find_path(s, t):
predecessor = t
while(predecessor):
print(predecessor)
predecessor = P[s][predecssor]
```
```
時間複雜度: O(|V|^3)
```
### 矩陣鏈乘積
給定一長度為n的矩陣鏈<A1,A2,...An>，對於i=1,2,…,n而言，矩陣Ai的維度為 pi-1*pi。找出一種方式對<A1,A2,...An>進行完全括號(fully parenthesized)以最少的純量乘法求出矩陣鏈乘積。
m[i, j]= 計算 Ai*Ai+1*...*Aj 所需的最小相乘數
s[1..n, 1..n]來記錄哪一個指標 k 造就了m[i, j]的最小成本。
> 轉移方程
> m[i, j] = 0 if i = j
> m[i, j] = min{m[i, k] + m[k+1, j] + Pi-1PkPj} for i<=k<j if i != j
```cpp=
MATRIX_CHAIN_ORDER(p):
n <- length[p] - 1
for i <- 1 to n:
m[i, i] = 0
for l <- 2 to n: //從連續兩個相乘遞迴到n個
for i <- 1 to n-l+1:
j = i+l-1
m[i, j] = INF
for k <- i to j-1: // 決定從哪個點分割最好
q <- m[i, k] + m[k+1, j] + Pi-1*Pk*Pj
if m[i, j] > q:
m[i, j] = q
s[i, j] = k
return m, s
PRINT_OPTIMAL_PARENS(s, i, j)
if i=j
then print “A”i
else
print “(“
PRINT_OPTIMAL_PARENS(s, i, s[i,j])
PRINT_OPTIMAL_PARENS(s, s[i,j]+1, j)
print “)”
```
```
時間複雜度: O(n^3)
```
### 最佳二元搜尋樹
Input: 陣列p[i=1...n],代表已排序序列K=<k1,...,kn>被搜尋機率，陣列q[i=0...n],代表搜尋目標di不在K中的機率,其中ki<di<ki+1
Output: 最佳二元搜尋樹的期望搜索成本e[1,n],各子樹樹根root
w[i, j] 表 i~j項機率總和
e[i, j] 表最佳二元搜尋樹的期望搜索成本，其中i>=1，j<=n，j>=i-1
> 轉移方程
> e[i, j] = q[j] if j == i-1
> e[i, j] = min{e[i, k-1] + e[k+1, j] + w[i, j]} i<=k<=j if j != i-1
```cpp=
OPTIMAL-BST(p, q, n):
for i <- 1 to n+1:
e[i, i-1] <- qi-1
w[i, i-1] <- qi-1
for l <- 1 to n:
for i <- 1 to n-1+1:
j <- i+l+1
e[i, j] <- INF
w[i, j] <- w[i, j-1] + pj + qj
for r <- i to j:
t <- e[i, r-1] + e[r+1, j] + w[i, j]
if t < e[i, j]
e[i, j] <- t
root[i, j] <- r
return e, root
```
## Tree Search and Backtracking
### BFS
1. 設定起始節點為解答空間樹的根節點，標示根節點，並建立一個只包含啟始節點的佇列(queue)
2. 拜訪並檢查佇列的第一個節點是否為目標節點goal node。若是，則輸出目標節點所對應的解答並停止
3. 移除佇列中的第一個節點。若此節點可以擴展出未標示過的子節點，則標示這些節點，並將其加入**佇列的尾端**
4. 若佇列為空，則回報無解答並停止。否則，跳至步驟2繼續執行
### DFS
1. 設定起始節點為解答空間樹的根節點，標示根節點，並建立一個只包含啟始節點的堆疊(stack)
2. 拜訪並檢查堆疊頂端的節點是否為目標節點。若是，則輸出目標節點所對應的解答並停止
3. 移除堆疊頂端的節點。若此節點可以擴展出未標示過的子節點，則標示這些節點，並將其一一加入**堆疊的頂端**
4. 若堆疊為空，則回報無解答並停止。否則，跳至步驟2繼續執行
### 登山搜尋
DFS + **評估函數**
1. 設定起始節點為解答空間樹的根節點，標示根節點，並建立一個只包含啟始節點的堆疊(stack)
2. 拜訪並檢查堆疊頂端的節點是否為目標節點。若是，則輸出目標節點所對應的解答並停止
3. 移除堆疊頂端的節點。若此節點可以擴展出未標示過的子節點，則標示這些節點，並根據由評估函數所計算的優先順序將其一一加入堆疊的頂端，**優先順序低的先加入**。
4. 若堆疊為空，則回報無解答並停止。否則，跳至步驟2繼續執行
### 最佳優先搜尋
BFS + DFS + 評估函數
>相對於僅具有區域(也就是僅限於某分支)最佳觀點的登山搜尋演算法，最佳優先搜尋演算法具有全域最佳的觀點。
1. 設定起始節點為解答空間樹的根節點，標示根節點，並建立一個只包含啟始節點一個元素的堆積(heap)
2. 拜訪並檢查堆積中**優先順序最高**的節點是否為目標節點。若是，則輸出目標節點所對應的解答並停止
3. 移除堆積優先順序最高的節點。若此節點可以擴展出未標示過的子節點，則標示這些節點，並根據由**評估函數所計算的優先順序**將其一一加入堆積中
4. 若堆積為空，則回報無解答並停止。否則，跳至步驟2繼續執行
### backtracking (八皇后問題)
```cpp=
PutQueen(i, n):
j = 0
while j < n:
if i列j行可以放置棋子:
q[i] = j
if i == n-1:
return q
else:
PutQueen(i+1, n)
j++
return false // 如果每一行都放不了就 goback
```
## Branch-and-Bound
* Branch: 找出好的機制在搜尋解答的過程中，擴展解答空間樹產生分支。
* Bound: 找出好的機制設定上界與下界，使許多分支終止搜尋。
此算法可以在平均狀況下不需要窮舉搜尋，然而在worst case仍需要非常龐大的解答空間數
## A* algorithm
最佳優先搜尋+評估函數
* \* 代表 real
* 可被視為一個分支定界演算法的特例，**當第一個可行解被走訪時**，所有在堆積(優先佇列)中的節點都被終止
* 評估函數: f(n) = g(n) + h(n)
* g(n): 從root至節點n的當前成本。
* h(n): 從節點n到目標節點的評估的未來成本。
* h∗(n): 從節點n到目標節點的==實際的未來成本==。
* f∗(n): 從root至節點n再到目標節點的==實際成本==。
* h(n)≤h∗(n)
## 問題分類: P、NP、NP困難與NP完全問題
* 一套定義演算法複雜度的方法
### DTM vs NTM
DTM 就是指 deterministic Turing machine
NTM 則是指 non-deterministic Turing machine
>我們當今的電腦架構是比較接近 deterministic Turing machine (DTM)，和它對比的是 non-deterministic Turing machine (NTM)，deterministic 的中文稱為決定性，所以 non-deterministic 就是非決定性，如果給予 Turing machine 某個 state 和某個 symbol 下它的下一步如果只有一種可能，那我們就稱它為 deterministic Turing machine (DTM)，所以上述的讀取頭每次就依照當下特定的 symbol 和 state 然後「決定」下一步應該要怎麼動作。
> 但是 non-deterministic Turing machine (NTM) 就不拘於此，針對某個 state 和某個 symbol 它的下一步可能會有很多種，它會是一個分支，它可能同時要向右移3格，又同時要向左移動2格，所以你可以想像一下你的讀寫頭一分為二，然後再各自進行自己的任務，這個分支可以有無限多個，只要最後有某個分支到達 halt state，我們就解完問題了，這就是 non-deterministic Turing machine (NTM)。
>
> DTM 只是 NTM 的特例，所以 NTM 比 DTM 擁有更快的計算速度，但這裡不要誤會喔！不管是 DTM 和 NTM 能解的問題是一樣多的，而且在數學上可以將 NTM 轉換成 DTM，**只是它們解決相同問題所用到的時間複雜度不一樣**，不過這就很關鍵。
### P vs NP
* 一群演算法用DTM來做計算所需時間是 polynomial time，那這類演算法或問題被稱為Ｐ問題
* 一群演算法用NTM來做計算所需時間是 polynomial time，那這類問題被稱為NP問題，或是以**驗證解的難度**來界定，如果用DTM來驗證一組解是否正確只需要 polynomial time，那這個問題就是一個NP問題
>毋庸置疑的，NP問題必定包含P問題，在DTM之下為 polynomial time 可解決的，在NTM之下也必定是 polynomial time 可解決的，但是P問題會等價於NP問題嗎？（P=NP?）這個問題到目前為止還是數學界無法證明的問題，目前既不能證明P=NP也不能證明P≠NP
### NP Complete
> 當數學家試圖解決 NP=P? 問題時，導出了一個重要的概念— NP-Complete問題。1971年美國 Stephen A. Cook提出了Cook-Levin理論，這個數學理論指出**任何一個NP裡面的問題都可以在 polynomial time 內，使用DTM，將之化約成「一個布林方程式是否存在解」的問題**，這個被化約的問題又稱為布爾可滿足性問題（SAT），我們稱SAT問題為NP-Complete問題。
滿足以下兩個條件:
1. 它本身是一個NP問題
2. 所有的NP問題都可以用DTM在 polynomial time 內化約成為它。
>這個概念非常強大，假設我證明了SAT是P問題，就等於今天我隨便拿到一個NP問題就可以在 polynomial time 內把問題轉換成SAT，然後再用 polynomial time 把SAT解掉，所以所有的NP問題都只是P問題了，也就是P=NP，因此NP-Complete問題就是解決 P=NP 的關鍵，**如果可以證明NP-Complete問題為P問題，就可以間接證明P=NP**。
已知的NPC問題：
1. 支配集合問題(dominating set problem)
無向圖上，選定數點，其餘點皆與之相鄰，稱作「支配集」
2. 點覆蓋問題(vertex cover problem)
無向圖上，挑選數個點，碰觸到所有邊，這些點就叫做一個「點覆蓋」
3. 集團問題(clique problem)
團(clique)是一個圖中兩兩相鄰的一個點集，或是一個完全子圖（complete subgraph）
分團問題是問一個圖中是否有大小是k以上的團。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個團，所以這個問題屬於NP
4. 著色問題(chromatic coloring problem)
「著色」。一張圖的特定元件，通通塗上顏色，相鄰元件不可同色。
「最小點著色」是顏色數目最少的點著色，可能有許多種。「最小著色數」是最小點著色的顏色數目。
5. Steiner tree
所謂的 Steiner Tree Problem, 是一組無向圖G(V,E)中, 給定一組 terminals, 然後我們必需在G上找到一個 minimum spanning tree, 這個 tree 必需滿足下面要求
* 它必需 span 所有的 terminals
* 它可以包含非 terminal 的點, 這些點稱之為 steiner node, 如圖1的B, E, F
* 它的 total cos t必需為最小
13. SAT問題
14. 3SAT問題：如 E(x)=(x1∨x2∨¬x4)∧(¬x3∨x4∨¬x5)，變數三個一組
15. 集合覆蓋問題
16. 0/1背包問題
17. 旅行推銷員問題
18. 分割問題
### NP hard
* 滿足**所有的NP問題都可以用DTM在 polynomial time 內化約成為它**即可
* NP-Complete問題是NP-Hard 問題的一種特例
> 事實上，目前科學界普遍相信P≠NP，所以遇到NP-Complete的問題，就直接標註這是一道難題，使用近似解吧！這是一個不怎麼樂觀的看法，難道說我們真的無法把這樣的難題給解決掉了嗎？也未必啦！仔細想想我們也許還有另外一個方法，只要我們創建一個NTM就可以把這些難題給解決掉啦！不過連量子電腦都普遍不被認為是一個NTM
## Flow Networks
Flow Networks is a weighted, directed graph c(x, y) >= 0 (x到y的weight)
flow需要滿足下列特性：
1. Capacity constraint: 從x流到y的水流不能比c(x, y)還大 f(x, y) <= c(x, y)
2. Skew symmetry: 若從x到y有w單位的flow 則f(x, y) = w, f(y, x) = -w
3. Flow conservation: 除了起點與終點外，每個節點進入的水流要等於出來的水流
### Ford-Fulkerson Algorithm
1. Residual Networks(剩餘網路）
* 紀錄Graph上的邊還有多少的容量可以讓flow流過
* Residual Networks也是一個directed graph，其中edge的capacity以residual capacity取代
* 而剩餘網路中最重要的就是如果從x到y有w的水流過，那麼在剩餘網路上會產生一條從y到x的邊具有w的capacity
因為: cf(y, x) = c(y, x) – f(y, x) = c(y, x) + f(x, y) = f(x, y) = w
> 剩餘網路最重要的物理意義就是讓"水資源流動的路線可以重新被分配"
2. Augmenting Paths
在Residual Networks中，所有能夠讓水從起點流到終點的路徑就是Argument Paths
### 演算法概念
不斷的在Residual Networks上找Augmenting Paths
1. 用BFS找Augmenting Paths(確保找到最短的路徑)
2. Augmenting Paths上最小的一條Residual capacity加入總流量
3. 再以這條flow更新Residual Networks
直到找不到Augmenting Paths時停
```cpp=
FORD-FULKERSON(G, s, t):
for each edge(u, v) in E:
f[u, v] <- 0
f[v, u] <- 0
while there exists a path p from s to t in the residual network Gf:
Cf(p) <- min{Cf(u, v):(u, v) is in P}
for each edge(u, v) is in P:
f[u, v] <- f[u, v] + Cf(p)
f[v, u] <- f[v, u] - Cf(p)
c[u, v] <- c[u, v] - Cf(p)
c[v, u] <- c[v, u] + Cf(p)
```
###### tags: `考試複習`
Sign in with Wallet
Connect another wallet