[Algorithms] 4.4 Dijkstra algorithms

해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.

4.4 Dijkstra’s algorithm

4.4.1 An adaptation of breadth-first search

앞에서 본 BFS의 상황을 더 일반화해보겠습니다.
graph $G = (V, E)$, edge의 길이 $l_e$가 양수인 경우라고 가정해보겠습니다.

A more convenient graph

위 그림과 같이 그래프를 바꾸는 간단한 트릭을 통해 BFS를 적용할 수 있습니다.

바로 더미 노드를 추가해주는 것 입니다.(= G의 edges을 unit-length를 가지는 조각들로 쪼갭니다.)

즉, 기존의 $G$를 다음의 방법으로 새로운 $G’$를 만들어 줍니다.

any edge $e = (u, v)$ of $E$에 대하여 $u$와 $v$ 사이에 dummy nodes를 추가하여 길이가 1인 $l_e$의 edge로 대체합니다.

이렇게 변환한 $G’$는 우리가 관심있는 노드 집합 $V$에 대해서, 기존 $G$와 같은 distances를 유지할 수 있습니다.
중요한 사실은 $G’$가 모든 unit length를 가지므로, $G’$에 대해 BFS를 적용시켜 $G$에 대한 거리를 계산할 수 있게 됩니다.

Alarm clocks

앞서 본 dummy node 전략은 효율성 측면에서 단점이 있습니다.
$G’$가 더미 노드들이 많다 보니, 고려하지 않아도 될 노드들의 거리까지 계산하게 된다는 문제가 존재합니다.

$G’$의 정점 s로 부터 시작해서 BFS를 한다고 가정하겠습니다.(단위 분당 단위거리)
처음 99 동안은 S-A와 S-B를 따라서 지루하게 알고리즘을 progress 합니다.(끝없는 더미의 향연)
이런 지루한 과정은 재우고, 흥미로운 일이 일어날 때만 꺠우는 알림이 있으면 어떻게 될까요?
- 구체적으로, 기존 그래프 G에 존재하는 노드들 중 하나를 만나게 될 때를 의미합니다.

Alarm cloks algorithm의 Intuition을 살펴보겠습니다.
우선 처음 시작할 때, 두 개의 알람을 세팅해줍니다.

노드 A에 대해서는 $T=100$
노드 B에 대해서는 $T=200$

위 $T$값들은 estimated times of arrival로 현재 travered중인 엣지들 위를 기반으로 산정됩니다. A를 찾기 위해서 먼저 재웠다가 $T=100$때 깨우는 구조입니다. 이 시점에서, B에 도착 측정 시간(estimated times of arrival)은 $T=150$으로 변경되므로, 알람 또한 바꿔줘야 합니다.

일반적으로 $G$의 특정 모서리를 따라 BFS가 진행되고 있으며, $G$가 이동하는 모든 끝점 노드에 대해 해당 노드에 도착 예상 시간에 경보가 울리도록 설정됩니다. 이 중 일부는 BFS가 나중에 다른 곳에 도착하여 shortcuts를 찾을 수 있기 때문에 overestimates 일 수 있습니다.

앞의 사례에서 A에 도착하자마자 B로 가는 더 빠른 경로가 밝혀졌습니다. 하지만 경보가 울리기 전에는 흥미로운 일이 일어날 수 없습니다.
따라서 다음 경보음이 울리면 BFS에 의해 파형 전선이 실제 노드 $u ∈ V$로 도달하는 신호가 되어야 합니다. 이때 BFS가 u에서 새로운 에지를 따라 advancing을 시작할 수 있으며 해당 엔드포인트에 대해 경보를 설정해야 합니다.

Alarm clocks algorithm은 $G’$에서 BFS 실행을 정확하게 시뮬레이션합니다.

노드 s에 대해 시간을 0으로 alarm clock을 설정합니다.
그리고 Alarm이 더이상 없을 때 까지 반복합니다: node u의 경우, 다음 alarm이 T시간에 발생한다고 가정해보겠습니다.
- s에서 u까지의 거리를 T라고 하겠습니다.
- G에 있는 각 인접 v에 대해:
  - v에 대한 alarm이 없는 경우, time $T +l(u,v)$로 설정합니다.
  - V의 알람이 $T + l(u, v)$ 이상으로 설정되어 있는 경우, 이 이전 시간으로 재설정합니다.

Dijkstra’s algorithm

앞서 Alarm clocks algorithm은 edge lengths가 양의 정수인 모든 그래프에서 거리를 계산합니다.

이번 알고리즘인 Dijkstra,s algorithm에서 적합한 자료 구조는 priority queue(일반적으로 heap을 통해 구현) 입니다.
priority queue는 연결된 numeric key value(time)으로 nodes를 유지하며 다음의 작업을 지원합니다.

Insert: 집합에 새로운 원소를 추가합니다.
Decrease-key: 특정 원소의 키 값 감소를 수용합니다.
Delete-min: 가장 작은 키 값을 가진 원소를 반환하고, 집합에서 해당 원소를 삭제합니다.
Make-queue: 지정된 키 값을 사용하여 지정된 요소에서 우선 순위 대기열을 작성합니다. (많은 구현에서 이 방법은 요소를 하나씩 삽입하는 것보다 훨씬 빠릅니다.)

첫 번째, 두 번째는 알림을 설정해놓고, 세 번째는 어떤 알림이 울릴지 알려줍니다. 이 모든 것을 종합하면, Dijkstra's algorithm을 얻을 수 있습니다.

위 코드를 살펴보겠습니다.
먼저 dist(u)는 노드 u에 대한 현재 Alarm clock 설정을 나타냅니다. $∞$값은 알람이 설정되지 않았다는 뜻입니다.
또한 각 노드 u에 대한 중요한 정보 한 가지, 즉 s에서 u까지의 최단 경로에 있는 노드의 identity를 저장하는 특별한 어레이($prev$)도 있습니다. 이러한 back-pointers를 따라 최단 경로를 쉽게 재구성할 수 있으므로 이 어레이는 발견된 모든 경로를 간략하게 요약합니다.
최종 shortest-path tree와 함께 알고리즘 작동의 전체 예가 아래의 그림에 나와 있습니다.

다시 요약하자면, Dijkstra’s algorithm의 알고리즘은 regular queue 대신 priority queue를 사용하는 것을 제외하고, edge lengths만 고려하는 방식으로 노드에 우선순위를 지정하기 위해서 단지 BFS로만 생각할 수 있습니다.

이러한 관점은 알고리즘이 어떻게, 왜 작동하는지에 대한 구체적인 인식을 주지만, BFS에 의존하지 않는 보다 직접적이고 추상적인 파생이 존재합니다.

4.4.2 An alternative derivation

Compute shortest paths

최단 경로를 계산하기 위해서, 정점 s(start)로부터 점차 밖으로 확장해 거리와 최단경로가 알려진 그래프의 영역을 꾸준히 확장시키는 것 입니다.
이러한 확장은 먼저 가장 가까운 노드를 통합한 후, 더 멀리 있는 노드를 통해 질서정연하게 진행되어야 합니다.

구체적으로 구하는 방법은 다음과 같습니다.

known region은 s를 포함하는 꼭짓점 R의 일부 부분 집합입니다.
s를 포함하는 노드들의 집합 R이 될 때, 다음에 추가될 것은 s로부터 가장 가까우면서, R 밖에 있는 노드들이 되어야 할 것입니다.
이러한 노드들을 v라고 한다면, 어떻게 식별할 수 있을까요?
- s에서 v까지 가는 최단 경로 안에서 v 바로 이전의 노드를 u라고 하겠습니다.
- 모든 edge lengths가 양수라고 가정하겠습니다.
- u는 v보다 s에 가까울 것입니다. => u는 R에 들어있습니다.
- 그렇기에, s에서 v로 가는 최단 경로는 a known shortest path extended by a single edge라고 할 수 있습니다.

4.4.3 Running time

다익스트라의 알고리즘은 구조적으로 BFS와 동일합니다. 하지만 우선순위 큐가 BFS의 constant-time의 eject와 inject보다 계산적으로 더 까다롭기 때문에(계산량 더 많이 요구) 속도가 느립니다.

총 연산량은 $\vert V \vert$ determin와 $\vert V \vert$+$\vert E \vert$ insert/decreasekey으로 표현합니다. makequeue에 최대 $\vert V \vert$insert 연산이 들어가기 때문입니다.

이 시간 복잡도는 어떻게 구현하냐에 따라 다르게 표현될 수 있습니다. binary heap을 사용할 경우, 총 걸리는 시간은 $O((\vert V \vert+\vert E \vert)log\vert V \vert)$입니다.

Reference

Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)
http://www.math.caltech.edu/~2014-15/1term/ma006a/class7.pdf
https://www.cs.mcgill.ca/~pnguyen/251F09/BFScorrect.pdf
https://velog.io/@pa324/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-1xk1cw46t2