---
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 figure, 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.
## Solution
From z:
Step0 : 
Step1 : 
Step2 : 
Step3 : 
Step4(check negative) :
=>無負迴圈
#### $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 : 
Step1 : 
Step2 : 
Step3 : 
Step4(check negative)
=>有負迴圈($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 find, 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 efficient 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點):
但負環會影響其他點的距離,所以要排除非環的點
:拿掉沒有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$, 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 $\pi$ values and the vertices in set $S$ after each iteration of the $\bf{while}$ loop.
-- figure 24.2
-- figure 24.6
## 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
# P8
## Topic
根據投影片Unit09 p.12的Bellman-Ford的實作考量, 改進原本的演算法, 並寫Pseudo code
## 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) 和原版一樣
Sign in with Wallet
Connect another wallet