[MIT] 파이썬을 이용한 알고리즘의 이해 - 최단 경로 2 : 다익스트라

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

✔ 복습

 d[v]는 출발점 s에서의 현재까지 구한 최단 경로의 길이입니다. 완화 과정을 통해 d[v]는 최종적으로 s부터 v까지의 최단 경로의 길이인 δ(s, v)가 됩니다. Π[v]는 s부터 v까지의 최단 경로에서 v의 선행자를 의미합니다. 최단 경로 계산에서의 기본 연산은 완화 연산이라고 할 수 있습니다.

 

👀 완화 연산

Relax(u, v, w)
    if d[v] > d[u] + w(u, v):
        d[v] = d[u] + w(u, v)
        ∏[v] = u

 

⁉️ 완화의 안전성

• 귀납법을 이용한 간단한 보조정리
  : 완화 알고리즘은 불변 조건인 모든 v∈V에서 d[v]≥ δ(s, v) 임을 항상 만족합니다.
• 증명
  : 과정의 횟수에 대한 귀납법. RELAX(u, v, w)로 생각해보면 귀납 가정에 의해 d[u] ≥ δ(s, u) 이고, 삼각 부등식에 의해 δ(s, v) ≤ δ(s, u) + δ(u, v) 입니다. d[u] ≥ δ(s, u) 이고 w(u, v) ≥ δ(u, v) 이기 때문에 δ(s, v) ≤ d[u] + w(u, v) 가 됩니다. 그러므로 d[v] = d[u] + w(u, v)로 할당하는 것은 안전합니다.

 

 

 

✔ DAG에서의 최단 거리

⁉️ DAGs

: 순환이 없기 때문에 음의 순환이 있을 수 없습니다.

1. DAG를 위상 정렬합니다. u에서 v까지의 경로는 선형 순서에서 u가 v 전에 온다는 의미입니다.
2. 위상 정렬된 정점을 한 번 훑으면서 그 정점에서 나가는 간선에 대해 완화합니다.
   Θ(V + E) 시간이 걸립니다.

정점은 왼쪽, 왼쪽에서 오른쪽으로 위상 정렬

r의 처리 : ∞를 유지합니다. s의 왼쪽에 있는 모든 정점은 정의에 의해 ∞로 남을 것입니다.

s의 처리 : t : ∞ → 2 x : ∞ → 6

 

 

 

✔ 다익스트라 알고리즘

 각 간선 (u, v) ∈ E에 대하여, w(u, v) ≥ 0을 가정하고, 정점의 집합 S에 최단 경로의 값이 결정된 정점만을 유지합니다. 최소인 최단 경로 어림을 가지는 u 를 V − S 집합에서 반복적으로 선택하여, u 를 S 에 넣고, u 로부터 나가는 모든 간선에 대해 완화합니다.

 

⁉️ 의사 코드

• 전략
  : 다익스트라는 탐욕 알고리즘입니다. V-S에서 가장 가까운 정점을 선택하여 집합 S에 넣습니다.
• 타당성
  : 중요 관찰점은 집합 S에 정점 u가 추가될 때마다 d[u]=δ(s, u)가 된다는 것입니다.

 

⁉️ 다익스트라의 복잡도

• Θ(V) 번의 우선순위 큐 삽입 연산
• Θ(V) 번의 EXTRACT-MIN 연산
• Θ(E) 번의 DECREASE-KEY 연산

⁉️ 배열을 이용한 구현 : Θ(V · V + E · 1) = Θ(V^2+E ) = Θ(V^2 )

• Θ(V ) : 최소의 원소 추출
• Θ(1) : 키 감소 연산

⁉️ 이진 최소 힙을 이용한 구현 : Θ(V lgV + ElgV )

• Θ(lgV ) : 최소의 원소 추출
• Θ(lgV ) : 키 감소 연산

⁉️ 피보나치 힙 : Θ(V lgV + E)

• Θ(lgV ) : 최소의 원소 추출
• Θ(1) : 키 감소 연산 분할상환 비용