Johnson's Algorithm

Johnson演算法與矩陣相乘法、Floyd-Warshall演算法一樣，
是用來計算all-pairs的最短路徑，
而當圖的邊很少、也就是應用在sparse graph時，
Johnson演算法的效率會比其他兩種方法還要好。

Johnson演算法會使用到Bellman-Ford演算法與Dijkstra演算法，
而後者必須限制圖中沒有negative-weight edge，
因此必須使用reweight的方法，把所有edge weight變成non-negative。

給一個Graph G=(V,E)，
每條邊(u,v)∈E原本的weight為w(u,v)，
定義每條邊reweight後的結果為：
w'(u,v) = w(u,v) + h(u) - h(v)

（註：在本篇文章中，w'代表課本中的ŵ，δ'代表課本中的δ̂ 。）

h是一個V → R、對應頂點到實數的一個函數，
一般都會定義成最短路徑的值。

Introduction to Algorithms Fig. 25.1

Introduction to Algorithms Fig. 25.6

左圖為一開始的圖，
在這個圖之外新增一個新的source vertex s，
s到每個vertex的距離都初始化為0。


在Fig.25.1中，node裡的數字代表vertex編號，
而在Fig.25.6中，vertex編號寫在node的旁邊，
在每個vertex v中的值為 h(v) = δ(s,v)。












































Johnson演算法的執行順序為：

1.
首先要用Bellman-Ford演算法，
去計算s->其他vertex的最短路徑。
圖(a)為計算結果，
每個node裡的值為從s到該node的最短距離。

2.
計算w'(u,v) = w(u,v) + h(u) - h(v)，
去reweight圖中的每一條邊。
圖(b)為計算結果。

例：
w'(2,5)
= w(2,5) + h(2) - h(5)
= 7 + (-1) - (-4) = 10

3.
由圖中每一個點各自當成起點，
去執行Dijkstra演算法。
圖(c)~(g)為各自的計算結果，
每個node裡的值為δ'(u,v)/δ(u,v)。

δ'就是由w'計算出來的最短路徑，
δ(u,v) = δ'(u,v) + h(v) - h(u)。

簡單來說，
首先用w'去計算每個node斜線左邊的值（δ'），
而斜線右邊的值（δ）= 斜線左邊的值 + 圖(b)裡node的值（h(v)-h(u)）。

例：
圖(c)以vertex 1當作起點。
δ(1,3)
= δ'(1,3) + h(3) - h(1)
= 2 + (-5) - 0 = -3
因此vertex 3裡的值為 2/-3。

例：
圖(g)以vertex 5當作起點。
δ(5,2)
= δ'(5,2) + h(2) - h(5)
= 2 + (-1) - (-4) = 5
因此vertex 2裡的值為 2/5。