# HW11 - Q7
###### tags: `演算法`, `109-2`

## Question
參考新版Unit9投影片 p.12 實作考量，改進Bellman-ford速度(改進速度建議加在課本原程式裡)，寫下pseudocode。

Code (P.8)

P.12

## Mein Answer

### 序章．Bellman Ford 與他的計謀
Bellman Ford 是個壞蛋，一心只想把 Digraph 弄鬆
他想了解一張 Digraph 最多可以弄的多鬆
最終，他得到了結論，一個 Digraph 最少有 V-1 個 Edge 經過
所以，只要對 Digraph 施暴 V-1 次，就能確保 Digraph 鬆到不能再鬆。

然而，許多 Digraph 根本無法承受這種暴力，
還沒撐到 V-1 次就已經受不了了
好好的一個 Digraph，被 Bellman 這個大壞蛋糟蹋成這樣
教我們於心何忍？

我們無法阻止 Bellman 殘暴的行為
至少，我們可以做出一些行動，減少 Digraph 的痛苦


### 首之章．In each iteration of the first loop, is it necessary to do the relaxation for each edge $uv \in E$ ?
帶著沈重的心情，
我們開始檢討，真的有必要讓 Bellman 徹底的施虐嗎？
真的有必要在每一次施虐的時候都要拿到每一個 Vertex 嗎？
其實不然。
在前幾次 Relaxion，我們有改變的 d 值都只集中在開始點 s 的周圍
其他部分只要有涉及到無限大的都不會做改變。
所以，在前幾次施暴，只要針對與施暴過的 vertex 相接的就好了


### 二之章．Similarly, is it necessary to do the checking for each edge $uv \in E$ in the second loop?
讓我們繼續。
在施暴完後，是否還要再跑一次迴圈，再給 Digraph 一次尾刀？
我們深入研究了解，
這個行動是為了檢查這張 Digraph 是否有自我再生能力，可以無限鬆下去？
那麼，如果我們若已經確定這個 Digraph 不會有環、或不會有負權重
便可以不需要這次尾刀。

### 三之章．Is it necessary to do the relaxations exactly |V|-1 times?
我們可以想辦法了解 Digraph 到第幾次的時候會達到極限：
可以在 Digraph 被蹂躪之前先幫他拍張照
之後再來對比有沒有發生改變，
如果沒有，就表示已經是極限了，可以請 Bellman 饒過他了

> 延伸： Suppose that we choose the vertex order in Yen's algorithm uniformly at randomly (where A contains all the edges that go from a lower vertex in the permutation to a higher vertex). The expected number of passes is at most (V+1)/3.

### 賀知章．碧玉妝成一樹高，萬條垂下綠絲絛
以下為蘇東扣 改自講義 加上落落長的註解

// Bellman-Ford(G, s)
Initialize(G, s) // π[v]=NIL, d[v]=INFINITY; d[s]=0
for i = 1 to |V|-1: // how many times of relax
    db = clone of (d) // Opt3
    foreach edge (u, v) with weight w in (E[x which d[x] != 0] and its neighbors): // Opt1+3ex the order could be randomize
        (d[v], π[v]) = Relaxtion((u, v), w)
    if db == d: // Opt3: if d isn't updated, there's no need to relax more
        break 
if G contains cycle and E contains negative number: // Opt 2
    foreach edge (u, v) in E:
        if d[u] >= d[u] + w(u, v): // check if still relaxationable
            return false // ERROR! G has a negative cycle
return true

に向工程: 反通靈之術

G: Graph
E: Edges of G (aka G.E)
V: Vertices (aka G.V)
s: Starting Point

π: Previous Vertex
d: distance

縱然我們做了很多，但是演算法的 Worst Case 依然是 $O(|V||E|)$ 或是說 $O(mn)$
而在 Normal Case， V (or m) 的不會是完整的 Vertex 數，稍稍減低了 Digraph 的痛苦。

**※ 家暴專線 請撥 113 求助**


### Reference
- https://ieeexplore.ieee.org/document/8847727
- https://www.sciencedirect.com/science/article/pii/089396599390022F
- https://www.ams.org/journals/qam/1970-27-04/S0033-569X-1970-0253822-7/
- https://www.csie.ntu.edu.tw/~yvchen/f106-ada/doc/171130_Graph2.pdf
- https://ithelp.ithome.com.tw/articles/10209748
- http://alrightchiu.github.io/SecondRound/single-source-shortest-pathbellman-ford-algorithm.html
- https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Improvements