---
# System prepended metadata

title: Homework XII

---

---
title: Homework XII
---
# P1
[CLRS 3rd] Exercise 24.1-1 
## Topic
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 ﬁgure, and show the $d$ and $\pi$ 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/9NzXnjB.png)

## Solution
From z:
Step0 : ![](https://i.imgur.com/1xa5cjr.png)
Step1 : ![](https://i.imgur.com/eQvUIxa.png)
Step2 : ![](https://i.imgur.com/584pQiT.png)
Step3 : ![](https://i.imgur.com/apBCCcM.png)
Step4(check negative) :![](https://i.imgur.com/ebWVEmJ.png)
=>無負迴圈
#### $d$ values:
| $s$ |    $t$   |    $x$   |    $y$   |   $z$    |
|:---:|:--------:|:--------:|:--------:|:--------:|
| $\infty$| $\infty$ | $\infty$ | $\infty$ |     0    |
|    2    | $\infty$ |     7    | $\infty$ |     0    |
|    2    |     5    |     7    |     9    |     0    |
|    2    |     5    |     6    |     9    |     0    |
|    2    |     4    |     6    |     9    |     0    |
#### $\pi$ 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$ |

From s:
Step0 : ![](https://i.imgur.com/QUfnGF2.png)
Step1 : ![](https://i.imgur.com/NV3qjHH.png)
Step2 : ![](https://i.imgur.com/k5tKHXT.png)
Step3 : ![](https://i.imgur.com/r8FGFXZ.png)
Step4(check negative)![](https://i.imgur.com/Ye5TUAa.png)
![](https://i.imgur.com/aJxdrDz.png)
=>有負迴圈($t$->$x$->$z$)

#### $d$ values:
| $s$ |    $t$   |    $x$   |    $y$   |   $z$    |
|:---:|:--------:|:--------:|:--------:|:--------:|
|  0  | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
|  0  |     6    | $\infty$ |     7    | $\infty$ |
|  0  |     6    |     4    |     7    |     2    |
|  0  |     2    |     4    |     7    |     2    |
|  0  |     2    |     4    |     7    |    -2    |
#### $\pi$ 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$  |


# P2
[CLRS 3rd] Exercise 24.1-5
## Topic
Let $G=(V,E)$ be a weighted, directed graph with weight function $w:E\to \mathbb{R}$. Give an O(VE)-time algorithm to ﬁnd, for each vertex $v\in V$, the value $\delta$*$(v)=\min_{u\in V}$ {$\delta (u,v)$}.
## Solution
把所有點的距離設為無限
對所有的邊relax, 則對點v來說, v的距離保證會變成所有w(u, v)當中最小的值(有可能會更小, 但是看機率)
再對所有的邊relax, v的距離如果大於當前的min(w(u, v), w(u, v) + u.d), 就會更新距離, 就如同往上上層找到某點w, 使得w到v的距離是最小的

照這個道理, 只要重複|V| - 1次, 就代表每一點的距離都有考慮到上|V| - 1層的點, 而simple graph 最多也只有|V| - 1條邊, 所以可以得到每一點的最小距離
```pseudo=
Procedure (G,w) //G為有向圖且非負環 
    For all u ∈ V:
        u.d = ∞
    For i = 1 to |V| - 1 
        for each edge uv in E
            if v.d > min(w(u, v), w(u, v) + u.d)
                v.d = min(w(u, v), w(u, v) + u.d)
                v.π = u.π
``` 

# P3
[CLRS 3rd] Exercise 24.1-6 
## Topic
Suppose that a weighted, directed graph $G=(V,E)$ has a negative-weight cycle. Give an efﬁcient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.
## Solution
加入一個額外的點S與每一個vertex連接,且權重為零
用Bellman-Ford找一遍各點與S的最短路徑
負環與S的距離一定<0 (例圖包含S共4點):
![](https://i.imgur.com/mCNhuMJ.png)
![](https://i.imgur.com/4VBIAJc.png)
![](https://i.imgur.com/MCva0hW.png)
但負環會影響其他點的距離,所以要排除非環的點
:拿掉沒有child的點v,再檢查parent[v]是否有child
最後其他與S距離<0的點即為負環裡的點
```pseudo=
Bellman-Ford(G,s){
    INITIALIZE-SINGLE-SOURCE(G, s)
    for i = 1 to |V| - 1
        for each edge (u, v) ∈ E
            if d[v]>d[u]+w(u,v)
            d[v]<-d[u]+w(u,v)
            pi[v]<-u
            parent[u]<-v
}
Find_Cycle(){
    Bellman-Ford(G,s);
    for each v in G
        if d[v]<0
            Neg_Cycle<-v
    while(true){
        for v in Neg_Cycle
            if(v do not have child)
                Neg_Cycle.remove(v)
                continue;
            break;
    }
    print(Neg_Cycle)
}
```
# P4
[CLRS 3rd] Exercise 24.3-1 
## Topic
Run Dijkstra’s algorithm on the directed graph of $Figure\ 24.2$, ﬁrst 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 $\pi$ values and the vertices in set $S$ after each iteration of the $\bf{while}$ loop.

-- figure 24.2
![](https://i.imgur.com/bRYlub3.png)
-- figure 24.6
![](https://i.imgur.com/rpCMUzU.png)


## Solution
### $s$ as the source:
#### $d$ values:
| $s$ | $t$ |   $x$    | $y$ |   $z$    |
|:---:|:---:|:--------:|:---:|:--------:|
|  0  |  3  | $\infty$ |  5  | $\infty$ |
|  0  |  3  |    9     |  5  | $\infty$ |
|  0  |  3  |    9     |  5  |    11    |
|  0  |  3  |    9     |  5  |    11    |
|  0  |  3  |    9     |  5  |    11    |
#### $\pi$ values:
|  $s$  | $t$ |  $x$  |  $y$  |  $z$  |
|:-----:|:---:|:-----:|:-----:|:-----:|
| $NIL$ | $s$ | $NIL$ |  $s$  | $NIL$ |
| $NIL$ | $s$ |  $t$  |  $s$  | $NIL$ |
| $NIL$ | $s$ |  $t$  |  $s$  |  $y$  |
| $NIL$ | $s$ |  $t$  |  $s$  |  $y$  |
| $NIL$ | $s$ |  $t$  |  $s$  |  $y$  |

### $z$ as the source:
#### $d$ values:
| $s$ |   $t$    | $x$ |   $y$    | $z$ |
|:---:|:--------:|:---:|:--------:|:---:|
|  3  | $\infty$ |  7  | $\infty$ |  0  |
|  3  |    6     |  7  |    8     |  0  |
|  3  |    6     |  7  |    8     |  0  |
|  3  |    6     |  7  |    8     |  0  |
|  3  |    6     |  7  |    8     |  0  |
#### $\pi$ 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$ |


# P5
[CLRS 3rd] Exercise 24.3-4 
## Topic
Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v\in V$ . Give an O(V+E)-time algorithm to check the output of the professor’s program. It should determine whether the $d$ and $\pi$ attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.
## Solution
先檢查初始的root: **d[root]=0,π[root]=Nil**
root以外的點: **d[v]=d[π[v]]+c(π[v],v)**
若有點root無法通往的點: **d[v]=∞,π[v]=Nil**
**以上檢查為O(V)**

對每個點做relaxation檢查
```
if (d[π[v]]+c(π[v],v))>[v]
    d[v]=d[π[v]]+c(π[v],v)
```
**以上檢查為O(E)**

**時間複雜度:O(V)+O(E)=O(V+E)**

```pseudo=
int correct=1; //which means correct
if(d[root]!= 0 || π[root]!= NULL) 
    correct = 0; //which means incorrect
for(v=root to |V|-1)
    if (d[v]!= ∞)
        if(d[v]!= d[π[v]]+c(π[v],v))
            correct=0;
    else
        if(π[v]!=Nil)
            correct=0; 
for(check each edge) //relaxation
    if(d[v] > d[π[v]]+c(π[v],v)) 
        correct=0;
    
Output:
    if correct = 1 → correct
    if correct = 0 → incorrect    
```

# P6
[CLRS 3rd] Exercise 24.3-8 
## Topic
Let $G=(V,E)$ be a weighted, directed graph with nonnegative weight function $w:E\to$ {$0,1,...,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
## Solution

```pseudo
DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    Q = G.V //build priority queue
    while !Q.empty()
        u = EXTRACT-MIN(Q)
        for each vertex v in Adj[u]
            if v.d > u.d + w(u, v)
                v.d = u.d + w(u, v)
                v.parent = u
                Change-Priority(Q,v)
```
由於$w$介於0和W, 演算法當中的queue實做方式可以更改

Q改用長(V-1)W+1的set陣列(bucket)
初始化的時候一樣把點的parent和距離初始化
建priority queue的時候把每個點的距離當作key, 存在Q[key]裡面
s放在Q[0], 其他點因為距離 == $\infty$先不放進來


由於圖無負邊, 可保證Change-Priority後v的距離不會小於u的距離
所以迭代完Q[0]~Q[Q.size()-1]就可以對所有點的邊Relax

EXTRACT-MIN改為find和erase, 如果set用hash實做可在O(1)完成
Change-Priority改為erase和insert, 可在O(1)完成

```pseudo
DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s) //v.parent=NIL, v.d = infintie, s.d = 0 
    Q = G.V //build priority queue O(V)
    for i = 0 to Q.size()-1 //O((VW)
        if u = Q[i].find() //found node in Q[i]
            Q[i].erase(u)
            for each vertex v in Adj[u]
                if v.d > u.d + w(u, v)
                    if v.d != infinite //initialized node not in bucket
                        Q[v.d].erase(v) 
                    v.d = u.d + w(u, v)
                    v.parent = u
                    Q[v.d].insert(v)
```
迴圈次數: O(VW)
對E個邊Relaxation: O(E)
總體時間複雜度: O(VW + E)
# P7 
[CLRS 3rd] Exercise 24.4-2
## Topic
Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

$x_1 -x_2\leq \ 4$
$x_1 -x_5\leq \ 5$
$x_2 -x_4\leq -6$
$x_3 -x_2\leq \ 1$
$x_4 -x_1\leq \ 3$
$x_4 -x_3\leq \ 5$
$x_4 -x_5\leq \ 10$
$x_5 -x_3\leq -4$
$x_5 -x_4\leq -8$
## Solution
找feasible solution:加入一個x0當sorce做Bellman-Ford，最後的最小值集合就是feasible solution
因為會形成負迴圈($x1,x4,x2,x3,x5,x1$)，所以沒有feasible solution
![](https://i.imgur.com/ROv5fjP.png)
![](https://i.imgur.com/1XyDDrh.png)



# P8
## Topic
根據投影片Unit09 p.12的Bellman-Ford的實作考量, 改進原本的演算法, 並寫Pseudo code
![](https://i.imgur.com/Gb9mZTC.png)

![](https://i.imgur.com/75GIp7N.png)

## Solution
1. 給一條邊(u, v), 若在上次迭代u.d沒有改變, 則v.d不會因u.d而改變, 因此只需要在u.d改變的下一次迭代對v的邊 Relax, 不需要對每條邊Relax
2. 若迭代到第V次還有距離可以更新則一定有負邊, 不需要額外檢查每條邊
3. 當完全沒有點的距離改變就可以停止迭代, 

實做方法:
<pre>    建立一個queue, 把距離更新過的點放進去, 並在每次加入新的點之前放入-1區隔迭代次數
    最多迭代到第V次, 若迭代到第V次還有距離可以更新則可以return False
    若某次迭代後queue裡只有-1而沒有其他點就可以停止迭代
</pre>
```pseudo=
Bellman-Ford(G, s)
    Initialize(G, s) //parent, distance
    Q is a empty queue
    Q.push(-1)
    Q.psuh(s)
    for i = 1 to |V| 
        if Q.size() == 1
            break
        Q.pop()
        Q.push(-1)
        while(Q.front()!=-1)
            u = Q.pop()
            for each edge uv in E
                if v.d > u.v + w(u, v)
                    if i ==|V|
                        return False
                    v.d = u.d + w(u, v)
                    v.parent = u
                    Q.push(v)
    return True
```

時間複雜度:O (VE) 和原版一樣