H-Log
[알고리즘] Dijkstra 알고리즘 본문
반응형
Single source shortest path 문제 (단일 출발점 최단 경로 문제)
질문
- A에서 D까지의 경로가 있나?
- 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까지의 거리
- Vf에 S추가 → Dist(S) = 0 (S와 S 자기 자신의 거리)
- 모든 노드와 S 사이의 거리를 비교
- 모든 노드 중 S와 가장 가까운 노드를 Vf에 추가. (추가된 노드 = t)
- 모든 노드마다 S와의 거리 / S와 t를 거쳤을 때의 거리 각각 비교
- 2개의 거리 중 더 짧은 거리를 선정
- 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)
반응형
'dev-log > cs' 카테고리의 다른 글
[양자 컴퓨팅과 보안] 큐빗 (0) | 2024.04.16 |
---|---|
[양자 컴퓨팅과 보안] 양자 컴퓨터 (0) | 2024.04.16 |
[알고리즘] Greedy 알고리즘 (0) | 2023.10.21 |
[알고리즘] 정렬 알고리즘 (0) | 2023.10.21 |
[알고리즘] Divaide-and-Conquer (0) | 2023.10.21 |
Comments