The Bellman-Ford Algorithm

此演算法用來解決single-source最短路徑的問題，
而Graph裡edge的weight可以是負值，
不過此演算法不適用有negative-weight cycle的Graph。

Introduction to Algorithms Fig. 24.4

如上圖，總共有5個node，
因此共需執行4次 => (b)~(e)。

(a)
一開始的圖，s為source，
要計算從s到每個點的最短路徑，
到每個點的距離初始化為無窮遠。

s  t  x  y  z
0  ∞  ∞  ∞  ∞

之後每次都要從「該次結果不是∞」的node出發，
也就是檢查不是∞的node的out edge，
計算其他node與「source」的距離，並取最小值。

而一開始只有s不是∞，
因此接下來要從s出發，去計算其他node與s的距離。

(b)
我們做一個表格來計算node之間的距離。

    s  t  x  y  z
    0  ∞  ∞  ∞  ∞    <-- 上次計算的結果
s->    6     7       <-- 從s出發，計算其他node到source的距離
------------------
    0  6  ∞  7  ∞    <-- 取最小值即為這次計算的結果

因為這次計算的結果，
t,y的值不為∞，
因此接下來要分別從t,y出發，
去計算其他node與「source」的距離。

雖然s的值也不為∞，
但不需要重新計算，待會會說明理由。

(c)
    s  t  x  y  z
    0  6  ∞  7  ∞    <-- 上次計算的結果
t->       11 14 2    <-- 從t出發，計算其他node到source的距離
y->       4     16   <-- 從y出發，計算其他node到source的距離
------------------
    0  6  4  7  2    <-- 取最小值即為當次計算的結果

要特別注意的是，
我們剛剛一直強調的是、其他node與「source」的距離，
而不是與「該node」的距離。

因此，t->x表格中填的值，也就是node x裡填的值，
是t本身的值(source到t的距離)、再加上t->x的距離。
=> 6+5=11

在這次的計算結果，
全部的node都不是∞了，
因此下次要從所有node出發，
去檢查這些node的out edge。

有一個小訣竅，
在下次計算的表格中，
只要重算「在這次計算之後，值有改變的node」即可。

例如，在這次的計算中，
s,t,y的值跟上次(b)計算的結果一樣，
因此在下次的計算中，
可以不用重算s,t,y，
直接把上次的結果抄上去即可，以節省時間。

而s的值從頭到尾都是0，
因此只有第一次loop需要計算從s出發的out edge，
之後就不需要再重新計算。

(d)
    s  t  x  y  z
    0  6  4  7  2    <-- 上次計算的結果
t->       11 14 2    <-- t值沒變，直接照抄上去
x->    2             <-- 從x出發，計算其他node到source的距離
y->       4     16   <-- y值沒變，直接照抄上去
z->       9          <-- 從z出發，計算其他node到source的距離
------------------
    0  2  4  7  2    <-- 取最小值即為當次計算的結果
在這次的計算結果，
t有改變，因此下次要重新計算從t出發的out edge。

(e)
    s  t  x  y  z
    0  2  4  7  2
t->       7  10 -2
x->    2            
y->       4     16
z->       9        
------------------
    0  2  4  7  -2
       x  y  s  t    <-- parent(π)即為最小值的該node

圖中有5個node，因此共需執行4次，
這次是第4次，計算就完成了。