http://i.imgur.com/jrsHj3H.jpg
我的答案為
ＴＴＦＴＴ
但 (a) (d) (e) 不太確定
(a)
這題不太確定是在問single source還是all pair
如果是single source的話應該可以化成Dijkstra
這樣會比Bellman_Ford快吧
(d)
因為乘上2不會改變原本的大小關係？
(e)
我的直覺選True
但不太確定希望有高手幫忙解惑

a要稀疏矩陣 再加上Johnson's algo才比較快

A false reweight 是指johnson algo但Johnson's algo 時間複雜度是(bellman+ dijkstra)

我看錯了 看成all paird對吧 e再想想

E 我今天才剛要看 看有沒有其他人會可以回答@@

感覺看完了也不太會選 囧

我覺得E是對的耶 C都+1應該沒差吧?

E應該是對的喔 因為所有加一之後 切集還是最小切集我錯惹 要視該切集有幾條邊決定 即使是最小切集如果他擁有的邊過多 每個邊+1後就可能不是最小切集了

我覺得這題就是要考人懂不懂reweight 為什麼不能直接用全部的邊統一加上某個值shift的function 來做，從這個角度下去想，就會知道他DE為什麼這樣出了