[알고리즘] Dijkstra 알고리즘

Single source shortest path 문제 (단일 출발점 최단 경로 문제)

질문

1. A에서 D까지의 경로가 있나?
2. A에서 D까지의 경로가 하나 이상 있다면, 어느 경로가 최단인가?

• 경로의 길이: 경로에 있는 연결선의 가중치(weight)들의 합
• 소스(source): 경로에서의 첫 시작 노드(vertex) ⇒ S라고 한다
• 도착점(destination): 경로에서의 마지막 노드

Dijkstra 알고리즘

• 방향 그래프 : G=(V, E)
• 가중치 함수 (cost 함수) : W(e)
• 시작 노드 : S (Source)
• 방안 : 시작 노드 S를 기준으로, 다른 모든 노드로의 최단 거리를 구한다 (Greedy)
• ⇒ 어떠한 정점을 거쳐가는게 빠른지, S에서 직접 가는게 빠른지 비교가 필요하다

Dijkstra 과정

• 집합 Vf : 선정된 노드 집합 / V-Vf : 선정되지 않은 집합 / DIST(n) : S-n까지의 거리

1. Vf에 S추가 → Dist(S) = 0 (S와 S 자기 자신의 거리)
2. 모든 노드와 S 사이의 거리를 비교
3. 모든 노드 중 S와 가장 가까운 노드를 Vf에 추가. (추가된 노드 = t)
4. 모든 노드마다 S와의 거리 / S와 t를 거쳤을 때의 거리 각각 비교
5. 2개의 거리 중 더 짧은 거리를 선정
6. 3번으로 loop하다가 V == Vf 일 때 중지

*선정된 노드가 Vf에 추가되며 t가 변경된다

*결과

Prim / Dijksta 비교

• Prim : 각 도시 잇는 도로 건설 가장 싼 가격
  • Vertex : 각 도시
  • Weight on each edge (v, w) : v-w간의 도로 공사비
• Dijkstra’s : 중앙 위성(방송국)에서 각 지역 위성(방송국) 간의 통신할때 가격 빠른 시간
  • Vertex : 각 인공위성(방송국)
  • Weight : 통신 시간

시간 복잡도 = O(n^2)