[MIT 6.006 정리] Lec 16. 그래프 (최단 경로 알고리즘_ 다익스트라 알고리즘)

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

* 최단 경로 알고리즘의 기본 구조 Recap

• d[v] : 출발점 s 부터 정점 v 까지의 (현재 시점에서의) 최단 경로의 길이
  • d[s] = 0, d[v] = inf.  (for any v) 로 초기화 후, 완화(relaxation) 과정을 통해 d[v] 값을 줄여 나감
  • 모든 정점 v 에 대해 d[v] = delta[v] (출발점에서 해당 정점까지의 실제 최단 경로(a shortest path) 의 길이) 로 수렴할 때까지 반복 후 알고리즘 종료
• 선행자 ∏[v] : 출발점 s 부터 v 까지의 최단 경로에서 v 의 선행자
  • 이 선행 관계를 역추적해서 따라가면 최단 경로를 재구성할 수 있음

def relax(u, v, w):
    if d[v] > d[u] + w(u,v):  ## v로 가는 기존보다 더 빠른 길을 발견
        d[v] = d[u] + w(u,v)
        pi[v] = u
        

 

• 완화(relaxation) 과정의 안전성 증명
  • 어떤 특정한 간선에 대해 완화를 했는데 그 결과로 delta(s,v) 보다 더 작은 값을 얻어낼 가능성이 없는지...! (없어야 함!)
  • [lemma 를 이용한 증명]

 

 

* 비순환 유향 그래프 (Directed Acyclic Graph, DAG) 의 최단 경로 알고리즘

• 순환이 없는 유향 그래프!
  • 특히 음의 순환(negative cycle) 에 대해 고민할 필요가 없으므로 문제가 간단해짐
  • 음의 가중치(negative weight) 은 가질 수도 있음
• 1) 그래프를 위상 정렬(topological sort) 함: 정점 u 에서 v 로의 경로는 u 가 v 보다 이전에 온다는 것을 의미함
• 2) 위상 정렬 결과 선형 순서를 갖게 되면, 정렬된 순서대로 (왼->오) 정점을 훑어주며 각 정점에서 나가는 간선에 대해 완화를 수행  ==>  모든 정점에 대해 최단 경로를 구할 수 있게 됨
  • 1), 2) 단계 각각이 O(V + E) 의 시간 복잡도를 가지므로, 총 시간 복잡도는 O(V + E)
• 어떤 정점을 출발점으로 잡아도 동작한다는 점!  -->  일단 위상 정렬을 한 후, 어떤 정점에서 시작할 지를 정할 수 있음

 

* 다익스트라 알고리즘 (Dijkstra algorithm)

• 모든 간선의 가중치가 0 또는 양수 (non-negative) 값을 갖는 그래프에 대해서만 적용 가능! (순환은 있어도 됨~)
• 출발점에서 시작하여 탐욕적으로 (in greedy manner) 최단 경로를 만들어 내는 greedy algorithm
• [pseudo-code for dijkstra]

def dijkstra(G,W,s):
    initialize(G, s)  # 정점 s 를 출발점으로 지정 == d[s]=0 & d[others]=inf
    S <- []           # 최단 경로를 구한 정점들의 집합 S
    Q <- V[G]         # 아직 처리되기 전의 정점들의 집합 Q (Priority Queue 로 구현)
    while Q != []:
        u <- EXTRACT_MIN(Q)           # 각 정점의 d[] 값이 비교 대상!
        S <- S U {u}
        for each vertex v in Adj[u]:  # 정점 u 에서 나가는 간선들에 대해 완화 수행
            relax(u,v,w)
        

• 완화 과정을 통해 우선순위 큐에서 각 정점들이 갖는 우선순위 값 (d[u]) 을 갱신해나감...!
• 최소 힙을 사용하여 우선순위 큐를 구현할 경우, 알고리즘의 총 복잡도는 O(V log V + E log V)
  • 1) O(V) = 우선순위 큐 Q 에 아직 방문하지 않은 (전체) 정점들을 삽입
  • 2) O(V log V) = EXTRACT_MIN 연산을 |V| 번 반복 O(V) * EXTRACT_MIN 수행에 O(log V)
  • 3) O(E log V) = 완화 과정에서 각 정점에 해당하는 키(key) 감소 연산 O(E) * 연산 한 번에 O(log V)
• 피보나치 힙(Fibonacci heap) 을 사용하여 구현할 경우, 총 O(V log V + E) 로 줄일 수 있다...!
  • EXTRACT_MIN 연산을 O(log V) & 키 감소 연산을 O(1) 분할 상환 시간 만에 수행 가능