[Algorithms] Dijkstra's Algorithm | 다익스트라 알고리즘

Dijkstra's Algorithm

다익스트라 알고리즘

- 0 이상의 Weight만을 허용하는 Weighted Graph상에서 Shortest Path를 찾아내는 알고리즘이다.
  (가중치가 음수인 경우는 Bellman-Ford Algorithm (URL)으로 해결할 수 있다.)
- 다익스트라 알고리즘은 시작 정점에서 다른 모든 정점까지의 간선들을 Greedy선택하며 계산해나간다.
- Prim's Algorithm (URL)과 유사한 알고리즘 구조를 갖고 있다.

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

※ Prim's Algorithm - Dijkstra's Algorithm
- 두 알고리즘 모두, Greedy하게 가장 짧은 간선을 골라가며 계산해나가는 것은 동일하다
- Prim's 알고리즘의 경우, 근본적으로 최소 신장 트리를 구성하는 알고리즘으로,
  새로운 정점을 포섭할 때, 집합 \(S\)에서 가장 짧은 거리에 있는 정점을 고른다.
- Dijkstra's 알고리즘의 경우, 근본적으로 시작 정점에서 모든 정점으로의 최단 거리를 계산하는 알고리즘으로,
  새로운 정점을 포섭할 때, 시작 정점에서의 거리가 가장 짧은 거리에 있는 정점을 집합 \(S\)에 포함시킨다.
- 프림 알고리즘에서 매력 함숫값은 현재 상태에서 방문하지 않은 정점을 연결하는데 드는 최소 비용이다.
- 다익스트라 알고리즘에서 매력 함숫값은 현재까지 계산된, 시작 정점에서 방문하지 않은 정점까지의 최소 거리이다.

---

Mechanism (원리)

Phase	Description
(a)	- 시작 정점 \(r\)까지의 최단 거리를 0으로 초기화하고,   나머지 정점까지의 최단 거리는 모두 \(\infty\)로 초기화한다.
(b)	- 시작 정점 \(r\)을 집합 \(S\)에 포함시킨다. - 집합 \(S\)에 인접한 정점들로 향하는 가중치들을 계산하여 저장해둔다.   (인접한 3개의 정점에 이르는 가중치는 각각 8, 9, 11이다.) - 정점에 기록된 수치값은, 시작 정점 \(r\)에서 해당 정점까지 이르는데 최단 거리다.
(c)	- 8로 계산되어 있는, 최단 거리가 가장 짧은 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 집합 \(S\)로 포함시킨 후,   최단 거리가 \(\infty\)였던 정점의 최단 거리가 18로 업데이트됨을 볼 수 있다.  - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 9이다.   (현재 계산된 거리가 9, 11, 18에 해당되는 정점들이 집합 \(S\)에 포함되어 있지 않은 상태이다.) * 최단 거리가 \(\infty\)에서 바뀌는 것은 시작 정점 \(r\)에서 해당 정점으로의 경로가 최초로 발견된 경우이다.
(d)	- 최단 거리가 9인 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 집합 \(S\)에 포함시키자,   최단 거리가 18이었던 정점의 최단 거리가 10으로 업데이트됨을 볼 수 있다. - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 10이다.   (현재 계산된 거리가 10, 11에 해당되는 정점들이 집합 \(S\)에 포함되어 있지 않은 상태이다.) * 최단 거리가 \(\infty\)가 아닌 수에서 바뀌는 것은 이미 경로가 발견된 적이 있지만,   더 짧은 경로가 발견된 경우이다.
(e)	- 최단 거리가 10인 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 집합 \(S\)에 포함시키자,   최단 거리가 \(\infty\)였던 정점의 최단 거리가 12로 업데이트됨을 볼 수 있다. - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 11이다.   (현재 계산된 거리가 11, 12에 해당되는 정점들이 집합 \(S\)에 포함되어 있지 않은 상태이다.)
(f)	- 최단 거리가 11인 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 집합 \(S\)에 포함시키자,   최단 거리가 \(\infty\)였던 두 정점의 최단 거리가 모두 19로 업데이트됨을 볼 수 있다. - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 12이다.   (현재 계산된 거리가 12, 19, 19에 해당되는 정점들이 집합 \(S\)에 포함되어 있지 않은 상태이다.)
(g)	- 최단 거리가 12인 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 집합 \(S\)에 포함시키자,   최단 거리가 19였던 정점의 최단 거리가 16로 업데이트됨을 볼 수 있다. - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 16이다.   (현재 계산된 거리가 16, 19에 해당되는 정점들이 집합 \(S\)에 포함되어 있지 않은 상태이다.)
(h)	- 최단 거리가 16인 정점을 집합 \(S\)에 포함시킨다. - 이 정점을 포함시켰다 해서, 최단 경로가 업데이트되는 정점은 없다. - 현재, 집합 \(S\)에 포함되지 않고, 계산된 경로 길이 중 최단 거리는 19뿐이다.
(i)	- 최단 거리가 19인 정점을 집합 \(S\)에 포함시킨다. - 마지막 남은 정점까지 집합 \(S\)에 포함되었다.
(j)	- 집합 \(S\)의 원소의 개수가 \(|V|\)가 되었으므로, 다익스트라 알고리즘을 종료한다.

※ 다익스트라 알고리즘은 임의의 정점을 집합 S에 포함시킬 때,
   시작 정점 r에서 해당 정점까지의 최단 경로 계산을 끝냈다고 간주하기 때문에,
   음수의 가중치가 새로 나타나 최단 경로를 업데이트해야 하는 상황에 대응하지 못한다.

- 아래는 다익스트라 알고리즘이 제대로 작동하지 못하는 모습을 그린 그림이다.

- 이러한 예시에서, (c) 단계 이후, (d2) 단계로 진행하는 것이 옳지만,
  다익스트라 알고리즘에서는 집합 \(S\)의 진출 간선만을 고려하고,
  이미 집합 S에 포함되어 있는 정점에 대해서는 최단 경로를 다시 계산하지 않으므로
  (d1) 단계로 진행하여 오답을 이끌어내게 된다.
  (그림에서, 청록색 영역으로 색칠되어 있는 부분이 집합 \(S\)이다.)

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

dijkstra(G, r)
// G = (V, E) : Given Graph
// r : Starting Vertex
// S : Set of Vertices
// d[v] : Weight of shortest path vertex 'r' to vertex 'v'
// L(u) : Set for Adjacency Vertices of Vertex 'u'
{
    S = empty_set();
    
    for(u ∈ V)
        d[u] = ∞;
    d[r] = 0;
    
    while(S != V) {
        u = extractMin(V-S, d);
        S = S ∪ {u};
        for(v ∈ L(u))
            if(v ∈ V-S && d[u]+w(u, v) < d[v]) {
                d[v] = d[u] + w(u, v);   // Update with lighter cost
                prev[v] = u;
            }
    }
}

extractMin(Q, d[])
{
     // 집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}

- Prim's 알고리즘에서 \(\texttt{d[v]}\)에는 정점 \(v\)를 신장 트리에 연결하는 가중치가 저장되어 있는 반면,
  Dijkstra's 알고리즘에서 \(\texttt{d[v]}\)에는 정점 \(r\)에서 정점 \(v\)까지의 최단 경로의 가중치값이 저장되어 있다.

---

Performance (성능)

* \(\texttt{extractMin()}\)에서 Data Structure로 Min Heap을 채택할 경우
Time Complexity : \(O(|E|*\log |V|)\)

---

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

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