[MIT] 파이썬을 이용한 알고리즘의 이해 - 최단 경로 1 : 도입

 

 

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

 

 

✔ 최단 거리

: 가중치가 최소인 경로 p를 찾으려고 하는 것

⁉️ 동기

: A에서 B로 가는 가장 짧은 거리 구글 지도의 "길 찾기".

• 가중 그래프 G(V, E, W), W = E → R의 문제
  • V = 정점(도로의 교차점)
  • E = 간선(거리, 도로); 방향 간선(일반통행 도로)
  • W(U, V) = 간선 (u, v)의 가중치 함수(거리, 통행료)

⁉️ 알고리즘

1. 다익스트라 O(VlgV + E) : 음이 아닌 가중치를 가정. E=O(V^2)
2. 벨만-포드 O(VE) : 일반적인 알고리즘

 

 

 

✔ 가중 그래프

⁉️ 표기

: v0에서 vk까지의 경로 p를 의미합니다. (v0)는 v0에서 v0까지의 가중치 0인 경로를 의미합니다.

 

⁉️ 정의

u에서 v까지 최단 경로의 가중치를 다음과 같이 정의합니다.

 

⁉️ 단일 출발 최단 경로

 G(V, E), w와 시작 정점 S가 주어져 있을 때, S부터 각각의 v∈V까지의 δ(S, V )(와 최단 경로)를 찾아보면 다음과 같습니다.

d[v] : 현재의 가중치를 의미.(v로 가는 더 좋은 경로를 찾을 때마다 줄어듭니다.)

Π[v]  : v까지의 최선의 경로에서 바로 직전 정점.(Π[s] = NIL)

 

 

 

✔ 음의 가중치 간선

• 몇몇 적응에는 자연스럽습니다.(예: 가중치로 로그가 쓰이는 경우)
• 몇몇 알고리즘은 음의 가중치를 갖는 간선을 허용하지 않습니다.(예: 다익스트라)
• 음의 가중치를 갖는 간선이 있으면, 음의 사이클이 있을 수도 있습니다. ⇒ 최단 경로가 없을 수도 있습니다.

 

⁉️ 예시

 B→D→C→B(원점)은 −6 + 2 + 3 =− 1 < 0의 가중치를 갖습니다. 최단 경로 S→C (또는 B , D , E )는 정의되지 않습니다. B→D→C를 원하는 만큼 반복할 수 있기 때문입니다. 최단 경로 S→A는 정의되고 가중치 2를 갖습니다. 음의 간선이 있는 경우, 최단 경로 알고리즘은 음의 사이클을 찾을 수 있어야 합니다.(예: 벨만-포드)

 

⁉️ 최단 경로 알고리즘의 일반적인 구조(음의 사이클이 없는 경우)

⁉️ 복잡도

일반적인 알고리즘의 실행 과정입니다. v0와 v1에서 나가는 간선들은 4, v2와 v3에서 나가는 간선들은 2, v4와 v5에서 나가는 간선들은 1의 가중치를 갖습니다. n개의 정점이 있다고 하면 마지막은 2^(n/2)와 같은 가중치를 가질 것입니다. d(V(n-1))를 한 번 완화할 때마다 1씩 줄이게 되면 O(2^(n/2)) 시간이 걸리게 됩니다.

 

 

 

✔ 최적 부분 구조

: 최단 경로의 부분 경로는 최단 경로입니다. p=<v0, v1, ..., vk>를 최단 경로라고 하고 pij=<v0, vi+1, ..., vj>가 0≤i≤j≤k라고 하면 pij는 최단 경로입니다.

증명

만약 p'ij가 pij보다 작다고 하면, pij대신 p'ij를 사용하게 되면 p보다 작아집니다. →  모순

 

⁉️ 삼각 부등식

 모든 u, v, x ∈ X에 대해 δ(u, v) ≤ δ(u, x) + δ(x, v)입니다.

증명