# Week 13
:::info
:::spoiler Click to Open TOC
[TOC]
:::
# Question
:::info
:::spoiler Click to Open Question
:::
# Answer
## Q1
> - [name=chung]
:::spoiler **【題目】**
Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex z as the source. In each pass, relax edges in the same order as in the figure, and show the d and π values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm again, using s as the source.
:::
#### Using vertex z as the source
:::spoiler **【示意圖】**
:::
- d values:
| s | t | x | y | z |
| - | - | - | - | - |
| ∞ | ∞ | ∞ | ∞ | 0 |
| 2 | ∞ | 7 | ∞ | 0 |
| 2 | 5 | 7 | 9 | 0 |
| 2 | 5 | 6 | 9 | 0 |
| 2 | 4 | 6 | 9 | 0 |
- π values:
| s | t | x | y | z |
| - | - | - | - | - |
| NIL | NIL | NIL | NIL | NIL |
| z | NIL | z | NIL | NIL |
| z | x | z | s | NIL |
| z | x | y | s | NIL |
| z | x | y | s | NIL |
做一次Bellman-Ford檢查有無負迴圈，無負迴圈，return true
ANS: z - s - y - x - t
#### Change the weight of edge (z, x) to 4
:::spoiler **【示意圖】**
:::
- d values:
| s | t | x | y | z |
| - | - | - | - | - |
| 0 | ∞ | ∞ | ∞ | ∞ |
| 0 | 6 | ∞ | 7 | ∞ |
| 0 | 6 | 4 | 7 | 2 |
| 0 | 2 | 4 | 7 | 2 |
| 0 | 2 | 4 | 7 | -2 |
- π values:
| s | t | x | y | z |
| - | - | - | - | - |
| NIL | NIL | NIL | NIL | NIL |
| NIL | s | NIL | s | NIL |
| NIL | s | y | s | t |
| NIL | x | y | s | t |
| NIL | x | y | s | t |
做一次Bellman-Ford檢查有無負迴圈，(z,x),(x,t),(t,z)有負迴圈，return false
## Q2
> - [name=Mark]
**思路**
1. 題目要找的是某點到其他點的最小路徑，我們令它沒有負環、其他點不包含欲搜尋的原點
2. 用修改的 Bellman-Ford 來找，原先是找 Graph 的最小路徑，現在改為將所有點都做為原點搜尋一次
```cpp=
Bellman-ford(G,s)
Initialize(G,s)//𝜋[v] = NIL, d[v] = ∞, ∀ 𝐯, d[s] = 0
for 𝑖 = 1 to |𝑉|−1 do
for each edge 𝒖𝒗∈𝑬 do
if d[v] > min(w(u, v), w(u, v) + d[u])
then d[v] = min(w(u, v), w(u, v) + d[u])
𝜋[v] = u
```
Time complexity : $O(VE)$
## Q3
> - [name=songchiu]
:::spoiler **【題目】**
Exercise 24.1-6:
Suppose that a weighted, directed graph G = (V, E) has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.
:::
**【解題思路】**
由於邊的權重有負值，要改採$\text{Bellman-Ford}$來解決問題，並且對其稍做修改。
當找到負的權重時，就開始往回找，把整個環找出來，且紀錄各個點到$\text{result}$裡面
假設已跑過一次$\text{Bellman-Ford}$，已得到相關資訊(例如：$\pi$)
**【蘇都扣】**
```c++=
Initialize cycle[v]<-0, result[] as empty
for each edge uv ∈ E
if(d[v] > d[u] + w(u, v))
cycle[v] = 1 //set as true
set current <- v
result.push_back(v)
while cycle[ π[current] ] = 0
current = π[current]
cycle[current] = 1 //set as true
result.push_back(current)
return result
```
**【時間複雜度】**
最差情況為遍歷所有的邊，接著再回頭去找每個點，故時間複雜度為 $O(E+V)$
## Q4
> - [name=chung]
:::spoiler **【題目】**
Run Dijkstra's algorithm on the directed graph of Figure 24.2, first using vertex s as the source and then using vertex z as the source. In the style of Figure 24.6, show the d and π values and the vertices in set S after each iteration of the while loop.
:::
#### Using vertex s as the source
:::spoiler **【示意圖】**
:::
- d values:
| s | t | x | y | z |
| - | - | - | - | - |
| 0 | 3 | ∞ | 5 | ∞ |
| 0 | 3 | 9 | 5 | ∞ |
| 0 | 3 | 9 | 5 | 11 |
| 0 | 3 | 9 | 5 | 11 |
| 0 | 3 | 9 | 5 | 11 |
- π values:
| s | t | x | y | z |
| - | - | - | - | - |
| NIL | s | NIL | NIL | NIL |
| NIL | s | t | s | NIL |
| NIL | s | t | s | y |
| NIL | s | t | s | y |
| NIL | s | t | s | y |
#### Using vertex z as the source
:::spoiler **【示意圖】**
:::
- d values:
| s | t | x | y | z |
| - | - | - | - | - |
| 3 | ∞ | 7 | ∞ | 0 |
| 3 | 6 | 7 | 8 | 0 |
| 3 | 6 | 7 | 8 | 0 |
| 3 | 6 | 7 | 8 | 0 |
| 3 | 6 | 7 | 8 | 0 |
- π values:
| s | t | x | y | z |
| - | - | - | - | - |
| z | NIL | z | NIL | NIL |
| z | s | z | s | NIL |
| z | s | z | s | NIL |
| z | s | z | s | NIL |
| z | s | z | s | NIL |
## Q5
> - [name=LXS]
:::spoiler 題目
Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces v.d and v.π for each vertex v ∈ V. Give an O(V+E)-time algorithm to check the output of the professor’s program. It should determine whether the d and π attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.
:::
#### 【解題思路】
**分別驗證**
1. source.d = 0 且 source.π = NIL，即初始值正確
2. v.d = v.π.d + w(v.π, v) ∀ v ≠ s，最短路徑樹內weight正確
3. v.d = ∞ IFF v.π = NIL ∀ v ≠ s，最短路徑樹外正確
4. 在一次Relex後，所有v.d仍不變，即結果確實是最短路徑
#### 【Psuedocode】
```python=
def verify():
if source.d != 0 or source.π != NIL: return False
checked = [(True if v is source else False) for v in V]
for u, v in E: # Assume we can iterate all edges (v.π!=NIL)
if u == v.π:
if u.d + w[u][v] != v.d: return False
checked[v] = True
elif u.d + w[u][v] < v.d: return False # Can't be relax
for v in V:
if (v.d == math.inf) xor (v.π == None): return False
if False in checked: return False
return True
```
**Time Complexity:** $O(V+E)$
## Q6
> - [name=xian]
:::spoiler **【題目】**
Let $G = (V,E)$ be a weighted, directed graph with nonnegative weight function $w : E→{ 0 , 1 ,\cdots ,W}$ for some nonnegative integer $W$ . Modify Dijkstra’s algorithm to compute the shortest paths from a given source vertex $s$ in $O(WV + E)$ time.
:::
$\quad$
**【題目說明】**
給定一個有向無負值權重圖，利用Dijkstra演算法實作 $O(WV + E)$ 時間內的Single-Source Shortest Path.
**【解題思路】**
* 現在多了一個條件，所有邊的權重都在$W$以下而且沒有負的，要讓演算法加速成$O(𝑊𝑉 + 𝐸)$ ，最短路徑最多有 $V-1$ 個邊，邊的 weight 最大是 $W$，所以最大**可能**的 path weight 上限為 $(V-1)W$。
* 將source到任意點的距離可以暫時存進一個大小為 $VW$ 的 `bucket[]`，初始化`d[v]` = $\infty$，`d[source]` = $0$，( `bucket[i]`可以存放很多點，`bucket[i].top` 為最早進去的點)，接著從頭掃描 bucket，當看到 bucket 不為空時，就對那個 bucket 中的所有點的相鄰點做 Relaxation，其中`d[]`有被更新的所有點都會重新放回在 bucket 裡，直到`bucket[VW]`掃描完，這個做法會把所有邊跑一次，然後掃描完bucket要 $VW$ 次，所以複雜度是 $O(VW+E)$。
* 因為(`bucket[i]`所代表的意思為從 source 到 bucket 中任何的點的最小距離為i)，因此當我們對 `bucket[i]` 裡面的點的鄰邊做Relaxation時，並不需要擔心被鬆弛的點會被放到 `bucket[i]` 之前，因為做完Relaxation的點的值一定大於他的 $parent$(`buncket[i]`)，因此不須重複掃描 bucket，只需掃一遍即可。
**【蘇都扣】**
```cpp=
// v.inbucket 存放在bucket裡的位置，初始化為0
//d[v] : vertex v 和source的距離(權重)
//bucket[i] : 暫存d[v] = i 的所有vertex
//p[v]為v的parent
//w[u, v] : edge uv 的權重
Dijkstra_modified(source, W, G, adj){
bucket[0~VW] = NULL //bucket is queue of vector
d[v] = ∞ , p[] = null for all vertex v in G
d[source] = 0
bucket[0].push(source)
for i = 0 to VW:
while bucket[i] is not empty:
u = bucket[i].pop()
if u.inbucket == i: //確認u是否在正確的位置
for each vertex v in adj[u]:
if(d[v] > d[u] + w[u, v]): //relax
d[v] = d[u] + w[u, v]
p[v] = u
if(v.inbucket): v.inbucket = d[v] //假如v已經被放在bucket中，則更新inbucket的位置
bucket[d[v]].push(v)
return p;
}
```
$\bf 最短路徑即存在p中_\#$
## Q7
> - [name=yee]
::: spoiler 題目
課本 p.366 提到 ROD-CUT 問題，其中 BOTTOM-UP-CUT-ROD()的 pseudo code
是屬於 unit09_ppt 中 p.19、p.20 中的哪一項(Type I or Type II)?並且請將
BOTTOM-UP-CUT-ROD()的 pseudo code 改寫為另一種 Type。
:::
### 【TYPE I】
### 【TYPE II】
### 【課本的蘇都扣】
```cpp=
BOTTOM-UP-CUT-ROF(p,n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
q = -∞
for i = 1 to j
q = max(q,p[i] + r[j - i])
r[j] = q
return r[n]
```
### 【想法】
我認為課本的是屬於Type II
由第七跟八行可以看到一開始計算的值不一定正確
是從 r[j- i] 項中取出最大值後才傳入r[j]中
相當於藍點取前面正確的綠點去進行計算
### 【ROD-CUT Type I 蘇都扣】
:::spoiler 舊版(有誤)
```cpp=
BOTTOM-UP-CUT-ROF(p,n)
let r[0..n] be a new array
let s[0..n] be a new array //紀錄每個最佳子結構總和
r[0] = 0
s[0] = 0
for i = 1 to n
q = r[i - 1] + p[i - s[i]]
s[i] = (i - 1) + (i - s[i - 1])
if q <= p[i]
q = p[i]
s[i] = i
r[i] = q
return r[n]
```
:::
```cpp=
BOTTOM-UP-CUT-ROF(p,n)
let r[0...n] be a new array
r[0] = 0
for j = 0 to n - 1
q = -∞
for i = 1 to j + 1
q = max(q,p[i] + r[j - i + 1])
r[j + 1] = q
return r[n]
```
Sign in with Wallet
Connect another wallet