# Week 14
# Question
:::info
:::spoiler Click to Open Question
:::
# Answer
## Q1
> - [name=Mark]
**原本的Floyd-Warshall algorithm**
將$d(u,u)=0$，沒有負環的情況會正確，可能有以下情況
1. 有負權重的邊
2. 有迴圈，走一圈的路徑長$\geq 0$，取min的情況下仍是0
**題目的Floyd-Warshall algorithm**
將$d(u,u)=\infty$，求$d(u,u)<\infty$可能的情況
**Ans**
有迴圈，從u出發走一圈回到u的路徑長$\le\infty$，取min的情況下就會是$d(u,u)<\infty$
補充：**可以有負權重的邊**，這是可以同時成立的；但仍舊不能有負環，不然找不出最小路徑
## Q2
> - [name=chung]
:::spoiler 題目
Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:
> x1 -x2 ≤4
> x1 -x5 ≤5
> x2 -x4 ≤-6
> x3 -x2 ≤1
> x4 -x1 ≤3
> x4 -x3 ≤5
> x4 -x5 ≤10
> x5 -x3 ≤-4
> x5 -x4 ≤-8
:::
#### 【解題方法】
因為此題有負Weight，因此使用Bellman-Ford演算法檢驗是否存在負環，
如果有負環即表示無法得知各節點的最短路徑，feasible solution不存在。
【Bellman-Ford步驟】
1. 設定各點的權重初始值為無限大$∞$，起點$X_4$的初始值為0，
2. 從起點開始任選一個連接起點到其他點的邊，開始計算並更新起點到另一點的權重
3. 計算方式為：原頂點權重 ＋ 邊的權重
4. 結果若比該點權重的現值小時，權重就更新為新算出來的這個值。反之，則維持現值不更新。
由示意圖可知，x4 -> x2 -> x3 -> x5 -> x1 -> x4 會形成負環，
因此這個 constraints graph 沒有 feasible solution。
## Q3
> - [name=songchiu]
:::spoiler 題目
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.
:::
**【解題思路】**
找 $\text{negative-weight cycle}$ 只要去找上的教的$\text{matrix multiplication}$矩陣$L^{(s)}$的對角線上，第一次出現負值的地方。
$L^{(s)}$的$s$就是題目所要求的 $\text{minimum-length negative-weight cycle}$
$L$矩陣有可能會長的像這樣：
## Q4
> - [name=Xian]
:::spoiler **【題目】**
Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure $25.2$ and answer the following questions：
a. Show the matrix $D^{(k)}$ that results for each iteration of the outer loop.
b. List the vertices of one such shortest path from $v_6$ to $v_1$.
:::
$\;$
**【a小題】**
$\;$
**【b小題】**
根據a小題所解的答案，我們可以先從最後早發生更動的值開始尋找，因為這題要找$v_6 \rightarrow v_1$，所以先找最早更改[6,1]的k值。
* [6,1]最早更改發生在 $k=2$
* $6 \rightarrow 2 \rightarrow 1$
* [2,1]最早更改發生在 $k=4$
* $6 \rightarrow 2 \rightarrow 4 \rightarrow 1$
* [4,1]最早更改發生在 $k=0$，停止
**Ans:** $\quad 6 \rightarrow 2 \rightarrow 4 \rightarrow 1_\#$
## Q5
> - [name=LXS]
:::spoiler 題目
Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph of Figure 25.2. Show the values of h and ŵ computed by the algorithm.
:::
【作法】
1. 做Reweighting，使所有邊權重非負(Bellman-Ford初始`d[v]`設為0)，同時排除負迴圈的可能
2. 跑V次Dijkstra's Algorithm
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| d(v) | 0 | 0 | 0 | 0 | 0 | 0 |
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| d(v) | -4 | -3 | 0 | 0 | -1 | -8 |
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| d(v) | -4 | -3 | 0 | -1 | -5 | -8 |
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| d(v) | -5 | -3 | 0 | -1 | -5 | -8 |
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| p(v) | 4 | 6 | NIL | 2 | 4 | 3 |
| d(v) | -5 | -3 | 0 | -1 | -6 | -8 |
得出 Shortest-path tree
| v | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | --- | --- | --- | --- | --- | --- |
| h(v) | -5 | -3 | 0 | -1 | -6 | -8 |
W'(u,v) = W(u,v) + h(u) - h(v)
| (u,v) | (1,5) | (2,1) | (2,4) | (3,2) | (3,6) | (4,1) | (4,5) | (5,2) | (6,2) | (6,3) |
| ------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| w(u,v) | -1 | 1 | 2 | 2 | -8 | -4 | 3 | 7 | 5 | 10 |
| w'(u,v) | 0 | 3 | 0 | 5 | 0 | 0 | 8 | 4 | 0 | 2 |
做V次Dijkstra後
$\begin{pmatrix}
0 & 4 & \infty & 4 & 0 & \infty \\
0 & 0 & \infty & 0 & 0 & \infty \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 4 & \infty & 0 & 0 & \infty \\
4 & 4 & \infty & 4 & 0 & \infty \\
0 & 0 & 2 & 0 & 0 & 0
\end{pmatrix}$
W(u,v) = W'(u,v) - h(u) + h(v)
$\begin{pmatrix}
0 & 6 & \infty & 8 & -1 & \infty \\
-2 & 0 & \infty & 2 & -3 & \infty \\
-5 & -3 & 0 & -1 & -6 & -8 \\
-4 & 2 & \infty & 0 & -5 & \infty \\
5 & 7 & \infty & 9 & 0 & \infty \\
3 & 5 & 10 & 7 & 2 & 0
\end{pmatrix}$
## Q6
> - [name=yee]
:::spoiler 題目
Arbitrage is the use of discrepancies in currency exchange rates to transform one
unit of a currency into more than one unit of the same currency. For example,
suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen,
and 1 Japanese yen buys 0.0107 U.S. dollars. Then, by converting currencies, a trader
can start with 1 U.S. dollar and buy 49×2×0.0107 = 1.0486 U.S. dollars, thus turning a
profit of 4.86 percent.
Suppose that we are given n currencies c1, c2, … cn and an n×n table R of exchange
rates, such that one unit of currency ci buys R[i, j ] units of currency cj .
a. Give an efficient algorithm to determine whether or not there exists a sequence of
currencies <ci1, ci2, …, cik> such that R[i1, i2 ]×R[i2, i3 ]×…×R[ik-1, ik ]×R[ik, i1 ] > 1 .
Analyze the running time of your algorithm.
b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the
running time of your algorithm.
:::
### a.
#### 【解題思路】
$\text{將 n 種貨幣視為 n 個點}(c_i = v_i)\text{，先對原不等式取 log}\\
使得\ R[i_1, i_2 ]×R[i_2, i_3 ]×…×R[i_{k-1}, i_k ]×R[i_k, i_1 ] > 1\\
\Rightarrow lg(R[i_1, i_2 ]×R[i_2, i_3]×…×R[i_{k-1}, i_k ]×R[i_k, i_1 ])> 0\\
\Rightarrow lg(R[i_1, i_2])+lg(R[i_2, i_3])+...+lg(R[i_{k-1},i_k])+lg(R[i_k,i_1])>0\\
\text{同乘上}(-1)\\
\Rightarrow -lg(R[i_1,i_2])-lg(R[i_2,i_3])-...-lg(R[i_{k-1},i_k])-lg(R[i_k,i_1])<0\\
得w(v_i,v_j) = -lg(R[i,j])\\
\text{即產生一個有向圖}G = (V,E),(v_i,v_j)\ 存在\ E\ 且\ weight = -lg(R[i,j]))\\
先設\ v_0\ 可達所有點，且\ weight\ 都是\ 0
\text{，再透過 Bellman Ford 來找有沒有負環。}$
#### 【蘇都扣】
```cpp=
Bellman-Ford(G, s)
Initialize(G, s) //𝜋[v] = NIL, d[v] = ∞, ∀ 𝐯, d[s] = 0
for i = 1 to |V| - 1 do
for each edge 𝒖𝒗 ∈ E do
if d[v] > d[u] + w(u, v)
d[v] = d[u] + w(u, v)
𝜋[v] = u
for each edge 𝒖𝒗 ∈ E do
if d[v] > d[u] + w(u, v)
return False //G has a negative cycle
return True
```
#### 【時間複雜度】
建立一個G需花$O(n^2)$而這個G有$n^2$個edges，使得Bellman Ford需花上$O(n^3)$，$O(n^2 + n^3) = O(n^3)$
### b.
#### 【解題思路】
因為必定存在一負環，因此做完|V|次BELLMAN FORD後，必定會return False，並且可知哪點v可以被Relax，用𝜋[v]往前找，直到遇到第二次v停下就可以找到負環。
#### 【蘇都扣】
```cpp=
Bellman-Ford-Find-Negative-Cycle(G, s)
Initialize(G, s) //𝜋[v] = NIL, d[v] = ∞, ∀ 𝐯, d[s] = 0
for i = 1 to |V| - 1 do
for each edge 𝒖𝒗 ∈ E do
if d[v] > d[u] + w(u, v)
d[v] = d[u] + w(u, v)
𝜋[v] = u
for each edge 𝒖𝒗 ∈ E do
if d[v] > d[u] + w(u, v)
mark v
x = v
while 𝜋[x] is not marked
mark 𝜋[x]
x = 𝜋[x]
return marked nodes
return NIL
```
#### 【時間複雜度】
Bellman Ford要花$O(n^3)$，Print-Sequence要花$O(n)$，
$O(n^3 + n) = O(n^3)$
## Q7
> - [name=yee]
:::spoiler 題目
:::
### 【解題思路】
Transitive Closure 代表 (u,v) u可移動到v,
先透過一個GTC[u,v]的boolean matrix來存放原先的狀態
GTC[u,v] = 1 表示 有Transitive Closure,即 u 可移動到 v
GTC[u,v] = 0 表示 沒有Transitive Closure,即 u 不可能移動到 v
透過這個boolean matrix來記錄每個點的狀態
#### a.當插入一個 new edge時，如何更新G的狀態，且要在$O(V^2)$內
#### 【蘇都扣】
```cpp=
GTC is a boolean matrix to store Transitive Closure
(u,v) is a new edge to be added
Update-Transitive-Closure(GTC,u,v)
for each x ∈ V
if GTC[x,u] and !GTC[x,v]:
for each y ∈ V
if GTC[v,y]
GTC[x,y] = True
```
#### b.舉個例子使transitive closure更新需要花到$O(V^2)$
原GTC：
| | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 1 |
增加edge(4,1)：
| | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 1 |
#### c.用一演算法去更新加入n個邊後的transitive closure，且其時間複雜度在$O(V^3)$
#### 【蘇都扣】
```cpp=
GTC is a boolean matrix to store Transitive Closure
(u,v) is a new edge to be added
Update-Nedges-Transitive-Closure(GTC,u,v)
for each edge (u,v) ∈ E
if !GTC[u,v]
for each x ∈ V
if GTC[x,u] and !GTC[x,v]
for each y ∈ V
if GTC[v,y]
GTC[x,y] = True
```
worst case $O(v^3)$
Sign in with Wallet
Connect another wallet