최단 경로 (2)

Shortest Path (2)

Bellman-Ford Algorithm

- 벨만 포드 알고리즘은 엣지들의 relax 순서가 고정되어 있지 않아 이 순서에 따라 중간 과정이 여러 분기로 나누어지게 된다.

- Worst Case에 근접한 실행 예

- 슈도 코드

BELLMAN-FORD (G, w, s)

INITIALIZE-SINGLE-SOURCE(G, s);

for i = 1 to |V[G]| - 1 // |V[G]|는 n과 같은 의미이기 때문에 n - 1번 반복하라는 뜻과 같다.

for each edge (u, v) ∈ E[G]

RELAX (u, v, w); // 여기까지가 벨만-포드 알고리즘의 핵심 부분

for each edge (u, v) ∈ E[G]

if d[v] > d[u] + w(u, v) // 음수 사이클이 존재한다는 것을 의미한다.

return false;

return true;

-> 벨만-포드 알고리즘의 시간 복잡도는 반복 횟수인 (n-1)에 relax에 소요되는 시간인 m을 곱한 O(nm)이 된다.

벨만-포드 알고리즘의 Worst Scenario

- 다익스트라 알고리즘의 시간 복잡도인 O($n^2$) or O($mlogn$)에 비해 벨만 포드 알고리즘의 시간 복잡도인 O(nm)은 별로 효율적이라 할 수 없다.

- d[v]의 길이가 최악인 상태로 파란 원부분에 d[v]를 전달한 후 relax를 통해 계속 점진적으로 길이를 줄이게 된다면 파란 원부분의 모든 노드들도 계속하여 전부 길이를 업데이트해야 하는 불필요한 연산이 필요해진다.

- 이 문제를 해결하기 위해서는 d[v]의 길이가 최소가 될때까지 갱신을 하지 않고 기다렸다가 전달을 받으면 된다. 또한 이 해결방식은 벨만-포드 알고리즘에서 다익스트라 알고리즘으로 넘어가기 위한 생각의 진행 과정이기도 하다.

Dijkstra Algorithm

- 기본적으로 음수 가중치가 없다라고 가정하고 시작한다.

- s로 부터의 최단경로 길이를 이미 찾아낸 노드들의 집합인 S를 유지한다. S는 공집합으로 시작한다. S의 길이가 n이 된다면 프로그램을 종료하게 된다.

- Loop Invariant

u  S인 각 노드 u에 대해 d(u)는 이미 S에 속한 노드들만 거쳐 s부터 u까지 도달하는 최단 경로의 길이다.

- 다익스트라는 벨만-포드와는 다르게 기준 노드로부터 모든 엣지들에 대해 relax를 진행하는 것이 아니라 길이값이 최소인 노드를 찾고 최소인 노드로부터 나가는 엣지들만 relax연산을 수행한다.

- 다익스트라 알고리즘의 주요 관점은 이미 이전 라운드에서 선택되어 길이가 최소인 엣지를 relax한 노드는 두 번 다시 선택하지 않는다는 것이다.

- 다음에 relax할 노드를 찾을 때는 이미 relax를 수행한 노드들을 제외한 노드들 중 d[v]의 값이 최소인 노드를 찾아 그 노드를 기준으로 relax를 수행한다.

- 알고리즘의 진행 과정

- 슈도 코드

Dijkstra (G, w, s)

//초기화 파트 : O(n)

for each u ∈ V

d[u] = ∞;

π[u] = null;

S = null;

d[s] = 0;

//구현 파트

while | S | < n // 반복문은 n번 반복하게 된다.

find u  S with the minimun d[u] ( = δ(s, u) ) value; // 최소 경로를 찾는 과정 : 최대 O(n)을 넘지 않는다.

S = S ∪ {u};

for each u  S adjacent to u (u에 인접한 노드v) // degree(u)만큼 반복 = O(n)

//relax 파트 : O(1)

if d[v] > d[u] + w(u, v)

d[v] = d[u] + w(u, v);

π[v] = u;

-> 다익스트라 알고리즘의 시간 복잡도는 O($n^2$)이 된다.

- 우선순위 큐를 이용한 다익스트라

Dijkstra (G, w, s)

INITIALIZE-SINGLE-SOURCE(G, s);

S = null;

Q = V[G];

while Q가 공집합이 아닐 때 // Q는 최소 우선순위 큐이다.

u = EXTRACT-MIN (Q); // O(logN)의 시간이 소요된다.

S = S ∪ {u};

for each vertex v ∈ Adj[[u]

RELAX(u, v, w); // d(v)의 값이 감소하게 된다.

//RELAX작업을 한 후 깨진 힙의 구조를 복원하는 추가 절차가 필요하다.

//이 작업은 O(logN)의 시간이 걸린다.

-> 이 코드는 O(nlogn)의 시간 복잡도를 가지게 된다.

Dijkstra Algorithm 증명

- 정리 : S에 속하지 않은 노드들 중에서 d값이 최소인 노드 u에 대해 d(u)는 s부터 u까지 최단경로의 길이다.

- 증명

1) 정리가 아니라 가정한다면 s부터 u까지의 다른 최단경로가 존재한다는 것을 뜻한다.

2) 아래의 그림을 토대로 본다면 d(v) ≥ d(u)이기 때문에 가정이 모순된다.

3) d(u)가 최소인 노드 u( S)를 찾고 S에 u를 추가한다.

4) S가 변경되었기 때문에 다른 노드들의 d(v)값을 갱신하게 된다.

∴ 엣지 (u, v)에 대해 relaxation하게 된다면 Loop Inveriant가 유지된다는 사실을 알 수 있게 된다.

Dijkstra Algorithm의 시간 복잡도

- Prim Algorithm과 동일한 복잡도를 가진다.

- 우선순위 큐를 사용하지 않고 단순한 자료 구조를 사용할 경우 O($n^2$)가 된다.

- 이진 힙을 우선순위 큐로 사용할 경우 O($nlog_2n$ + $mlog_2n$)이 된다.

- Fibonacci Heap을 이용하게 된다면 O($nlog_2n+m$)시간으로 구현할 수 있다.