### Johnson`s algorithm範例

```Floyd-Warshall
algorithm
95360794 康峻岳
All-pairs shortest paths
• Input: Digraph G = (V, E), where |V| = n,
with edge-weight function w : E → R.
• Output: n × n matrix of shortest-path
lengths
δ(i, j) for all i, j ∈ V.
Floyd-Warshall algorithm
Define cij(k) = weight of a shortest path from
i to j with intermediate vertices
belonging to the set {1, 2, …, k}
Thus, δ(i, j) = cij(n). Also, cij(0) = aij
Floyd-Warshall recurrence
• cij (k) = mink {cij(k–1), cik(k–1) + ckj(k–1)}
intermediate vertices in {1, 2, …, k}
Pseudocode for FloydWarshall
• for k ← 1 to n
do for i ← 1 to n
do for j ← 1 to n
do if cij > cik + ckj
then cij ← cik + ckj
Time Complexity: O(n3)

Johnson’s algorithm
1. Find a vertex labeling h such that ŵ(u, v) ≥ 0 for all
(u, v) ∈ E by using Bellman-Ford to solve the difference
constraints
h(v) – h(u) ≤ w(u, v),
or determine that a negative-weight cycle exists.
• Time = O(VE).
2. Run Dijkstra’s algorithm from each vertex using ŵ.
• Time = O(VE + V2 lg V).
3. Reweight each shortest-path length ŵ(p) to produce
the shortest-path lengths w(p) of the original graph.
• Time = O(V2).
Total time = O(VE + V2 lg V)
Johnson’s algorithm
• Johnson’s演算法利用Reweighing來除去負邊，使得該

• Reweighing是將每個點v設定一個高度h(v)，並且調整

• 令δ‘(u,v)如此調整之後的最短距離，則原先的最短距離
δ(u,v)=δ‘(u,v)-h(u)+h(v)。
Johnson’s algorithm範例
4
3
7
8
1
-4
-5
2
6
9
Johnson’s algorithm範例
0
0
s
0
0

weight為0的邊

4
3
7
8
1
-4
-5
2
6
0
10
Johnson’s algorithm範例
0
-1
0
4
3
s
0
0
7
8
0
-5
1
-4
-5

2
-4
6
0
0
11
Johnson’s algorithm範例
-1
0

reweighting
0
4
10
13
-5
0
0
0
2
-4
2
0
12
Johnson’s algorithm範例
2/1
0
4
0/0
10
13
2/-3
0
0
2
0/-4
2
0

(Reweighting後的圖/原

2/0
13
Johnson’s algorithm範例
0/0
0
4
2/3
10
13
0/-4
0
0
0
2
2/-1
2
0/1
14
Johnson’s algorithm範例
0/4
0
4
2/7
10
13
0/0
0
0
0
2
2/3
2
0/5
15
Johnson’s algorithm範例
0/-1
0
4
2/2
10
13
0/-5
0
0
0
2
2/-2
2
0/0
16
Johnson’s algorithm範例
2/5
0
4
4/8
10
13
2/1
0
0
0
2
0/0
2
2/6
17
Johnson’s algorithm複雜度分析
• 執行一次Bellman-Ford。O(|V||E|)。
• 執行|V|次Dijkstra。
– 使用Fibonacci heap，總計
O(|V|2log|V|+|V||E|) 。
– 使用Binary heap，總計O(|V||E|log|V|)。
• 當|E|足夠小，比Floyd-Warshall快。
18

• http://www.csie.nctu.edu.tw/~sctsai/algo/n
otes/
• http://tinyurl.com/cglkn6
• http://www.csie.ntnu.edu.tw/~u91029/inde
x.html
```