[Algorithms] Johnson's Algorithm | 존슨 알고리즘

Johnson's Algorithm

존슨 알고리즘

- Bellman-Ford Algorithm (URL)과 Dijkstra's Algorithm (URL)을 Subroutine으로 사용하여
  Weighted Graph에서 존재할 수 있는 모든 (출발 정점, 도착 정점) Pairs에 대한 최단 경로를 계산해내는 알고리즘이다.
- Sparse Graph에 대해서는 Floyd-Warshall Algorithm (URL) 보다 우수한 성능을 보여준다.
- Time Complexity of Floyd-Warshall Algorithm : \(\Theta(|V|^3)\)
- Time Complexity of Johnson's Algorithm : \(O(|V|^2\log |V| + |V|*|E|)\)

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

---

Mechanism (원리)

Function	Definition
\(w(u, v)\) Function	- 정점 \(u\)에서 정점 \(v\)까지의 간선의 가중치 - \(w : E \to \mathbb{R}\) 인 함수   (즉, \(w\)는 간선의 가중치를 실숫값으로 반환하는 함수이다.)
\(w(p)\) Function	- 경로 \(p\)의 가중치의 합 - 경로 \(p = <v_0, v_1, \cdots, v_k>\)일 때,   \(w(p) = w(v_0, v_1) + \cdots + w(v_{k-1}, v_k)\) 이다.   (즉, \(w(p)\)는 \(w(u, v)\)가 Abstraction된 형태이다.)
\(\delta(u, v)\) Function	- 정점 \(u\)에서 정점 \(v\)까지의 "최단 경로"의 가중치의 합
\(h(v)\) Function	\(h : V \to \mathbb{R}\) \(h(v) = \delta(s, v)\) - 즉, \(h\)는 정점 s에서 정점 v까지의 최단 경로 길이를 반환하는 함수이다.) - 정점 \(s\)는 그래프 \(G\)에 임의로 새롭게 추가되는 정점이다.)
\(\widehat{w}(u, v)\) Function	\(\widehat{w}(u, v) = w(u, v) + h(u) - h(v)\) - \(u, v \in E\) 이며,    \(\widehat{w}(p) = \widehat{\delta}(v_0, v_k) \iff w(p) = \delta(v_0, v_k)\) 이다.   (즉, 경로 \(p\)가 \(\widehat{w}\)를 사용한, \(u\)에서 \(v\)까지의 최단 경로이면,   경로 \(p\)는 \(w\)를 사용한, \(u\)에서 \(v\)까지의 최단 경로이기도 하고, Vice Versa하다.) - 또한, 그래프 \(G\)가 \(\widehat{w}\)를 이용하여 Negative-Weight Cycle을 갖는다면,   \(G\)는 \(w\)를 이용하여 Negative-Weight Cycle을 가지고, Vice Versa하다.

---

1. Reweighting (가중치 조정)

Case 1) Graph \(G = (V, E)\)에 있는 모든 간선이 가중치 \(w\)가 음수가 아니면,
  Minimum Priority Queue에 속하는 Fibonacci Heap을 사용한 Dijkstra's 알고리즘 (URL)을
  각 정점에 대해 수행하여, 그래프 \(G\)에 존재할 수 있는 모든 (시작 정점, 도착 정점) Pairs의 최단 경로를 계산할 수 있다.

Case 2) Graph \(G = (V, E)\)에 음수값의 Cycle은 존재하지 않으면서, 가중치가 음수인 간선이 존재하면,
  음수가 아닌 가중치를 가진 간선들의 집합 \(\widehat{w}\)를 새로 정의하되, \(\widehat{w}\)는 아래 조건*을 만족해야 한다.

* \(\widehat{w}\)의 성립 조건
1. 그래프 \(G\)에 존재하는 모든 \((u, v) \in V\)에 대해,
  경로 \(p\)가 가중치 함수 \(\widehat{w}\)를 사용한 \(u\)에서 \(v\)까지의 최단 경로이면,
  \(p\)도 가중치 함수 \(w\)를 사용한 \(u\)에서 \(v\)까지의 최단 경로이고, Vice Versa 하다.

2. 모든 간선 \((u, v)\)에 대해 새로운 가중치 함수 \(\widehat{w}(u, v)\)는 음수가 아니다.

※ 새로운 가중치 함수 \(\widehat{w}\)는 \(O(|V|*|E|)\) 시간에 그래프 \(G\)를 Preprocessing 하여 얻어낼 수 있다.

※ Reweighting이 본래 최단 경로를 해치지 않음은 본 포스트의 Verification (검증) Section의 Lemma에서 증명한다.

---

2. Producing nonnegative weights by reweighting (가중치 조정을 통해 음이 아닌 가중치 만들기)

- 모든 간선 \((u, v) \in E\)에 대해, \(\widehat{w}(u, v)\)가 음이 아니어야 함에 유념하며 \(\widehat{w}\)를 계산하는데,
  \(G\)에 새로운 정점 \(s\)를 추가하여 \(G'\)을 만들고, 이에 대한 가중치 함수 \(w\)를 적절히 수정하여 \(\widehat{w}\)를 계산한다.

1) 새로운 정점 \(s\)를 \(V\)에 추가하여 새로운 그래프 \(G' = (V', E')\) 만들기

- 가중치 함수 \(w : E \to \mathbb{R}\)를 갖는 Weighted-Directed Graph \(G = (V, E)\)가 주어졌을 때,
  새로운 정점 \(s \notin V\)에 대해,
  \(V' = V \cup \{s\}\) 이고,
  \(E' = E \cup \{(s, v) : v \in V\}\)인
  새로운 그래프 \(G' = (V', E')\)을 만든다.
- 이때, \(G'\)의 각 정점에 표시된 값은 \(h(v) = \delta(s, v)\) 이다.
- 모든 \(v \in V\)에 대해 \(w(s, v) = 0\)이 되도록 가중치 함수 \(w\)를 확장한다.
- \(s\)는 진입 간선이 없으므로, \(s\)를 출발점으로 하는 최단 경로 외에는 어떠한 최단 경로도 \(s\)를 중간 경유지로 하지 않는다.
- \(G\)가 Negative-Weighted Cycle을 갖고 있지 않다면 \(G'\) 또한 Negative-Weighted Cycle을 갖고 있지 않으며,
  이는 Vice Versa 하다.


2) \(G'\)의 \(w\)를 기반으로 \(\widehat{w}\) 계산하기

- 모든 \(v \in V'\) 에 대해 \(h(v) = \delta(s, v)\) 를 정의한다.
- The Triangle Inequality(삼각 부등식, 본 포스트 하단 참조)에 의해,
  모든 간선 \((u, v) \in E'\) 에 대해 \(h(v) \leq h(u) + w(u, v)\)를 얻어낼 수 있다.
- 새로운 가중치 함수 \(\widehat{w}\)를 
  \(\widehat{w}(u, v) = w(u, v) + h(u) - h(v)\)에 따라 가중치를 조정하면,
  \(\widehat{w}(u, v) = w(u, v) + h(u) - h(v) \geq 0\)이고,
  이는 \(\widehat{w}(u, v)\)는 음수가 아님을 의미한다.
  (\(\widehat{w}\)의 성립조건 2번을 만족하게 된 것이다.)

---

3. Computing all-pairs shortest paths (존재할 수 있는 모든 (시작 정점, 도착 정점) 쌍의 최단 경로 계산하기)

- 그래프에 존재하는 모든 (시작 정점, 도착 저점) Pairs에 대한 최단 경로를 계산하기 위해,
  Johnson's 알고리즘에서는 Bellman-Ford 알고리즘 (URL)과 Dijkstra 알고리즘 (URL)을 Subroutine으로 사용한다.
- Jonhson's 알고리즘에서는 일반적으로 Graph Representation 방법으로 Linked-List를 사용한다.
- 모든 Pairs에 대한 최단 경로를 \(|V| \times |V|\) Matrix에 저장하여 리턴한다.
- Negative-Weighted Cycle이 발견될 경우, Error Message를 출력하고 프로그램을 종료한다.
  (세부 구현사항은 본 포스트의 Implementation (구현) Section에서 설명한다.)  

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

jonhson(G, w)
// G = (V, E) : Given Graph by Linked-List Representation
// w  : Weight Function
// w^ : Newly calculated Weight Function
// δ(a, b) : Length of Shortest Path Vertex 'a' to Vertex 'b' (Delta Function)
// δ^ : Newly calculated Delta Function
{
    compute G',
    where G'.V = G.V ∪ {s},
          G'.E = G.E ∪ {(s, v) : v ∈ G.V},
          w(s, v) = 0 for all v ∈ G.V;
          
    if(bellman_ford(G', w, s) == FALSE)
        throw "The input graph contains a negative-weight cycle";
    else {
        for(v ∈ G'.V)
            set h(v) to the value of δ(s, v) computed by the bellman_ford algorithm;
        for((u, v) ∈ G'.E)
            w^(u, v) = w(u, v) + h(u) - h(v);
            
        Let D = d_{uv} be a new n by n matrix
        
        for(u ∈ G.V)
            run dijkstra(G, w^, u) to compute δ^(u, v) for all v ∈ G.V
            for(v ∈ G.V)
                d_{uv} = δ^(u, v) + h(v) - h(u);
        return D;
    }
}

---

Performance (성능)

* Subroutine인 Dijkstra's Algorithm의 Data Structure로 Min Heap을 채택할 경우
Time Complexity : \(O(|V|^2\log |V| + |V||E|)\)

* Sparse Graph에 대해, Subroutine인 Dijkstra's Algorithm의 Data Structure로 Binary Min Heap을 채택할 경우
Time Complexity : \(O(|V||E|\log |V|)\)

---

Verification (검증)

Lemma. The Triangle Inequality (삼각 부등식)

그래프 \(G = (V, E)\)가 가중치 함수 \(w : E \to \mathbb{R}\)와 출발 정점 \(s\)를 가진 Weighted-Directed Graph이면,
모든 간선 \((u, v) \in E\)에 대해 아래가 성립된다.

\(\delta(s, v) \leq \delta(s, u) + w(u, v)\)

- 다른 말로 하면, "세 정점을 잇는 세 간선 중 2개의 가중치 합이 나머지 하나의 간선 가중치보다 크거나 같다."
  라는 의미의 정리이다.

pf) 출발 정점 \(s\)에서 정점 \(v\)까지의 최단 경로를 \(p\)라 하자.
이때, \(p\)는 \(s\)에서 \(v\)로의 어느 경로와 비교하더라도 가중치가 더 크지 않다. (최단 경로이므로)
특히, 경로 \(p\)는 출발 정점 \(s\)에서 정점 \(u\)까지의 최단 경로를 취하고 나서 간선 \((u, v)\)를 취하는 특정 경로보다
가중치가 같을 수 있을지언정, 절대 크지 않다. (\(p\)가 최단 경로라는 가정에 모순이 생기므로)

---

Lemma. Reweighting 작업은 최단 경로를 바꾸지 않는다.

pf) 경로 \(p = <v_0, v_1, \cdots, v_k>\) 일 때,
\(\widehat{w}(p) = w(p) + h(v_0) - h(v_k)\) 이다.
근거는 아래와 같다.

\(\widehat{w}(p) = \sum\limits_{i=1}^{k} \widehat{w}(v_{i-1}, v_i)\)
\(= \sum\limits_{i=1}^{k} ( w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_i) )\)
\(= \sum\limits_{i=1}^{k} w(v_{i-1}, v_i) + h(v_0) - h(v_k)\)
\(= w(p) + h(v_0) - h(v_k)\)

또한, \(h(v_0)\)와 \(h(v_k)\)는 경로와 관련이 없으므로, 가중치 함수 \(w\)를 사용했을 때,
\(v_0\)에서 \(v_k\)까지의 어떤 임의의 경로가 다른 경로보다 짧다면, 그 경로는 \(\widehat{w}\)을 사용하면 더 짧아지게 된다.
그리고 이러한 사실은 Vice Versa 하다.

그리고 그래프 \(G\)가 가중치 함수 \(\widehat{w}\)를 사용했을 때, Negative-Weight Cycle이 생긴다면,
\(G\)가 \(w\)를 사용했을 경우에도 Negative-Weight Cycle이 생기고, Vice Versa 하다.
\(v_0 = v_k\)인 어떤 임의의 Cycle \(c = <v_0, v_1, \cdots, v_k>\)가 있다 할 때,
\(\widehat{w}(c) = w(c) + h(v_0) - h(v_k)\)
\(=w(c)\)
이기 때문이다.

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)