Week 14

Question

Click to Open Question

Answer

Q1

• Mark

原本的Floyd-Warshall algorithm
將

$d(u,u)=0$，沒有負環的情況會正確，可能有以下情況

1. 有負權重的邊
2. 有迴圈，走一圈的路徑長
   $\ge 0$，取min的情況下仍是0

題目的Floyd-Warshall algorithm
將

$d(u,u)=\mathrm{\infty }$，求

$d(u,u)<\mathrm{\infty }$可能的情況
Ans
有迴圈，從u出發走一圈回到u的路徑長

$\le \mathrm{\infty }$，取min的情況下就會是

$d(u,u)<\mathrm{\infty }$
補充：可以有負權重的邊，這是可以同時成立的；但仍舊不能有負環，不然找不出最小路徑

Q2

• chung

題目

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. 設定各點的權重初始值為無限大
   $\infty$，起點
   $X_4$的初始值為0，
2. 從起點開始任選一個連接起點到其他點的邊，開始計算並更新起點到另一點的權重
3. 計算方式為：原頂點權重 ＋ 邊的權重
4. 結果若比該點權重的現值小時，權重就更新為新算出來的這個值。反之，則維持現值不更新。
   

由示意圖可知，x4 -> x2 -> x3 -> x5 -> x1 -> x4 會形成負環，
因此這個 constraints graph 沒有 feasible solution。

Q3

• songchiu

題目

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

• Xian

【題目】

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\to v_1$，所以先找最早更改[6,1]的k值。

• [6,1]最早更改發生在
  $k=2$
  • $6\to 2\to 1$
• [2,1]最早更改發生在
  $k=4$
  • $6\to 2\to 4\to 1$
• [4,1]最早更改發生在
  $k=0$，停止

Ans:

$6\to 2\to 4\to 1_{\mathrm{\#}}$

Q5

• LXS

題目

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後

$\left(\begin{array}{cccccc}0& 4& \mathrm{\infty }& 4& 0& \mathrm{\infty }\\ 0& 0& \mathrm{\infty }& 0& 0& \mathrm{\infty }\\ 0& 0& 0& 0& 0& 0\\ 0& 4& \mathrm{\infty }& 0& 0& \mathrm{\infty }\\ 4& 4& \mathrm{\infty }& 4& 0& \mathrm{\infty }\\ 0& 0& 2& 0& 0& 0\end{array}\right)$

W(u,v) = W'(u,v) - h(u) + h(v)

$\left(\begin{array}{cccccc}0& 6& \mathrm{\infty }& 8& -1& \mathrm{\infty }\\ -2& 0& \mathrm{\infty }& 2& -3& \mathrm{\infty }\\ -5& -3& 0& -1& -6& -8\\ -4& 2& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 5& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 3& 5& 10& 7& 2& 0\end{array}\right)$

Q6

• yee

題目

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.

【解題思路】

$$\begin{gathered} \text{將 n 種貨幣視為 n 個點}(c_i=v_i)\text{，先對原不等式取 log} \\ \mathrm{使}\mathrm{得}R[i_1,i_2]\times R[i_2,i_3]\times \dots \times R[i_{k-1},i_k]\times R[i_k,i_1]>1 \\ \Rightarrow lg(R[i_1,i_2]\times R[i_2,i_3]\times \dots \times R[i_{k-1},i_k]\times 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 \\ \mathrm{得}w(v_i,v_j)=-lg(R[i,j]) \\ \text{即產生一個有向圖}G=(V,E),(v_i,v_j)\mathrm{存}\mathrm{在}E\mathrm{且}weight=-lg(R[i,j])) \\ \mathrm{先}\mathrm{設}{v}_0\mathrm{可}\mathrm{達}\mathrm{所}\mathrm{有}\mathrm{點}，\mathrm{且}weight\mathrm{都}\mathrm{是}0\text{，再透過 Bellman Ford 來找有沒有負環。} \end{gathered}$$

【蘇都扣】

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停下就可以找到負環。

【蘇都扣】

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

• yee

題目

【解題思路】

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)$內

【蘇都扣】

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)$

【蘇都扣】

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)$