---
# System prepended metadata

title: Week 13

---

# Week 13

:::info
:::spoiler Click to Open TOC
[TOC]
:::

# Question
:::info
:::spoiler Click to Open Question
![](https://i.imgur.com/MZkx1Hz.png)
![](https://i.imgur.com/Gwv8Ud0.png)
:::

# 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.
![](https://i.imgur.com/oV1h9gi.png)

:::


#### Using vertex z as the source
:::spoiler **【示意圖】**
![](https://i.imgur.com/joz67Mv.jpg)
:::
- 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 **【示意圖】**
![](https://i.imgur.com/TdUZKkW.jpg)
:::
- 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.
![](https://i.imgur.com/7KcOSM9.png)
:::


#### Using vertex s as the source
:::spoiler **【示意圖】**
![](https://i.imgur.com/3AKpVZb.jpg)
:::
- 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 **【示意圖】**
![](https://i.imgur.com/H4Dt0BW.jpg)
:::
- 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.

![](https://i.imgur.com/ReDdARt.png =70%x)

**【解題思路】**
* 現在多了一個條件，所有邊的權重都在$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】
![](https://i.imgur.com/8MTazdk.png)

### 【TYPE II】
![](https://i.imgur.com/dGyCkqc.png)


### 【課本的蘇都扣】
```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]
```
