[MIT 6.006 정리] Lec 15. 그래프 (최단 경로 알고리즘_brute-force)

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

 

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

 

* 가중 그래프 (Weighted graphs)

• 간선에 가중치가 부여된 그래프 구조 (모든 간선이 갖는 가중치가 동일하지 않음!) -->  더욱 다양한 종류의 문제에 대해 적용 가능함
• G = (V, E, W)
  • W = 각 간선의 가중치를 나타내는 가중치 함수. W: E(간선 집합) → R(실수 집합)
  • 다익스트라 알고리즘; 음수가 아닌 (non-negative) 가중치를 가정. O(V log V + E) 의 복잡도.
  • 벨만-포드 알고리즘; 음수인 가중치에 대해서도 작동 가능. O(VE) 의 복잡도를 가짐.

+ 용어 정리

• 경로 path 는 간선의 나열과 같으며, 각 간선은 그래프에 존재해야 함 (간선 집합 E 의 원소여야!)
  • p = < v_0, v_1, ... , v_k >  &  (v_i, v_(i+1)) ∈ E  for 0 ≤ i < k
• 경로의 가중치 W(p) 는 간선의 가중치들의 합과 같음
  • W(p) = ∑_(i=0 to k-1) w(v_i, v_(i+1))
• 최단 경로 문제는 가중치가 최소인 경로 p 를 찾는 것
  • 가중치의 '개수'는 O(E^2) 에 제한되나, 가중치 '값'의 범위는 훨씬 넓은 범위에 걸쳐 (ex.지수적으로..) 존재할 수 있음!
  • 또한, 가능한 경로의 수가 지수적으로 존재한다는 점에서 일반적인 탐색/정렬보다 어려운 문제...!!
• v_0 --(p)--> v_k  :  정점 v_0 에서 v_k 로의 최단 경로를 찾는 문제에 대해,
  • (v_0) = v_0 에서 v_0 까지의 경로이며, 가중치는 0 임
  • 정점 u 에서 v 까지의 최단 경로 가중치 delta(u, v) = min{ w(p), u --(p)--> v } if any such path exists, or ∞ (inf)
  • d(v) : 현재의 정점 v 까지의 (누적) 가중치. 최종적으로 delta 값을 갖게 하는 것이 목표!
  • ∏[v] : 정점 v 까지의 최선의 경로에서 (v에 선행하는) 바로 직전 정점. 선행 관계를 나타냄~

 

+ 음의 가중치 (Negative weights)

• 근본적으로, 음의 가중치를 갖는 그래프가 왜(언제) 필요한가?
  • 예 1) 운전 시 경로에 따라 돈을 내거나 (통행료 지불) / 돈을 받게 (광고를 보는 것에 대한 보상= 역통행료) 되는 경우
  • 예 2) SNS 에서 좋아요 / 싫어요 flag 를 타고 이어지는 log
• 그래프에서 음의 사이클이 존재하는 경우, 최단 거리 delta 를 정의할 수 없는 정점들이 생기게 되는 문제  -->  해당 사이클에 특별한 처리 (종료 조건을제대로 설정하기 위해!) 를 해야 함!
  • 유한의 값을 갖는 정점에 대해서는 delta 값을 찾고, 나머지는 미결정 또는 -∞ 라고 표시해야 함!

 

* 최적 경로 알고리즘의 일반적인 구조 (brute-force, no negative cycle only)

• 정점 집합에 있는 모든 u 에 대해 d[v] = ∞ 로 초기화하고, 선행자 ∏[v] = NIL 로 설정. 
• 출발점 s 이 하나일 때 (single-source), d[s] = 0 으로 설정한 후, 간선 (u, v) 를 선택 & 완화(relax) 하는 과정을 반복함
  • 간선 (u, v) 의 선택은 Somehow... 이걸 어떻게 하느냐에 따라 다른 알고리즘이 됨!
  • 간선 (u, v) 를 완화(relax)  ==  if d[v] > d[u] + w(u,v) ==> d[v] = d[u] + w(u,v) & ∏[v] = u 으로 갱신
  • -- 기존의 d[v] 가 d[u] + w(u, v) 보다 크다면, v 로 가는 기존의 방법보다 더 나은 방법 (u를 거쳐가는 길!) 을 찾았다는 것!
  • 모든 간선에 대해 d[v] 가 d[u] + w(u,v) 보다 작거나 같아질 때 (= 어떤 간선에 대해서도 더이상 완화가 불가능할 때) 반복이 끝남~
• 종료 조건을 만족시키기 위해선 모든 간선에 대해 확인해봐야 하므로 O(E) 만큼의 비용 요구됨
  • 간선을 어느 순서로 선택할 지 신중하게 고려해서 알고리즘을 디자인 해야함! 
    -- 아니면 간선 완화하느라.. exponential time complexity 가 걸릴 수도...!!

 

+ 최적 부분 구조 조건

• 대부분의 최단 경로 알고리즘이 효율적인 복잡도를 얻기 위해 이용하는 기법
• Theorem 1: 최단 경로의 부분 경로는 최단 경로가 됨
• Theorem 2: (삼각부등식)

• 해당 두 조건을 이용해 위의 brute-force 알고리즘을 선형 시간 알고리즘으로 개선할 수 있음!