본 글에서는 최단 경로 알고리즘 중 "" 다익스트라 알고리즘 ""과 "" 플로이드 워셜 알고리즘 ""에 대해 살펴보고하며
""이것이 취업을 위한 코딩 테스트다"" 책을 바탕으로 작성한 글입니다.
- 다익스트라 알고리즘은 """ 한 지점 """에서 """ 다른 특정 지점 """까지의 최단 경로를 구해야 하는 경우에 사용되는 최단 경로 알고리즘입니다.
- 플로이드 워셜 알고리즘은 """ 모든 지점 """에서 """ 다른 모든 지점 """까지의 최단 경로를 구해야 하는 경우에 사용되는 최단 경로 알고리즘입니다.
1. 다익스트라 최단 경로 알고리즘
다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다.
▶ 알고리즘
알고리즘의 원리는 다음과 같습니다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3,4번을 반복한다.
▶ 우선순위 큐
다익스트라 최단 경로 알고리즘을 효율적으로 구현하기 위해서 힙 자료구조를 사용합니다.
힙 자료구조는 우선순위 큐(queue)를 구현하기 위하여 사용되는 자료구조입니다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제합니다.
| 자료구조 | 추출되는 데이터 |
| 스택(Stack) | 가장 나중에 삽입된 데이터 |
| 큐(Queue) | 가장 먼저 삽입된 데이터 |
| 우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
힙은 첫번째 원소를 우선순위로 설정하며 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 나눌 수 있습니다.
- 최소 힙(Min Heap): 값이 가장 낮은 데이터가 먼저 삭제
- 최대 힙(Max Heap): 값이 가장 큰 데이터가 먼저 삭제
▶ Python에서의 우선순위 큐 구현 방법 : PriorityQueue 혹은 heapq
일반적으로 heapq가 더 빠르게 동작하기 때문에 왠만해서는 heapq를 사용하는 것을 추천한다고 합니다.
'PriorityQueue'와 'heapq'는 모두 최소 힙에 기반합니다.
따라서, 만약 가장 큰 데이터가 먼저 삭제되기를 원한다면 음수 부호(-)를 붙여서 넣었다가 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 갑스으로 돌리면 됩니다.
'heapq'는 (거리 비용, 노드 번호) 순서대로 튜플로 구현되어 있습니다.
▶ Example
- [Step 1]. 시작 노드는 1번 노드라고 가정합니다.
- [Step 2] 먼저, 최단 거리 테이블을 초기화합니다.
1번 노드에서 출발하여 1번 노드까지의 최단 거리는 0, 나머지 노드에 대해서는 무한대로 초기화합니다.
노드 번호 1 2 3 4 5 6 거리 0 무한 무한 무한 무한 무한 우선순위 큐 (거리: 0, 노드: 1) - [Step 3-1] 우선순위 큐에 있는 원소는 (거리: 0, 노드 1) 하나이므로 이를 꺼냅니다.
그리고 1번 노드로부터 갈 수 있는 노드는 {2,3,5}로 이에 대한 최단 거리를 업데이트합니다.
노드 번호 1 2 3 4 5 6 거리 0 2 5 1 무한 무한 우선순위 큐 (거리:2, 노드: 2), (거리:5, 노드: 3), (거리:1, 노드: 4) - [Step 3-2] 우선순위 큐에 있는 원소 중 가장 짧은 거리를 갖는 노드는 4이므로 (거리:1, 노드: 4)를 꺼냅니다.
그리고 4번 노드와 인접한 노드는 {3,5}로 이에 대한 최단 거리가 업데이트 됩니다.
노드 번호 1 2 3 4 5 6 거리 0 2 4(1+3) 1 2(1+1) 무한 우선순위 큐 (거리:2, 노드: 2), (거리:5, 노드: 3), (거리: 4, 노드: 3), (거리:2, 노드: 5) - [Step 3-3] 우선순위 큐에 있는 원소 중 가장 짧은 거리를 갖는 노드 2와 5 중 하나를 선택합니다. 본 글에서는 노드 2를 선택하겠다고 가정하겠습니다.
그리고 2번 노드와 인접한 노드는 {3,4} 이지만 2번 노드를 거쳐서 갈 경우 거리가 각각 {5,4}로 현재 최단 거리보다 크기 때문에 업데이트 되지 않습니다.
노드 번호 1 2 3 4 5 6 거리 0 2 4 1 2 무한 우선순위 큐 (거리:5, 노드: 3), (거리: 4, 노드: 3), (거리:2, 노드: 5) - [Step 3-4] 우선순위 큐에 있는 원소 중 가장 짧은 거리는 노드 5이므로 (거리: 2, 노드: 5)를 꺼냅니다.
그리고 5번 노드와 인접한 노드는 {3,6}이며 5번 노드를 거쳐갈 경우 각각의 거리는 {3, 4}이므로 최단 거리가 업데이트 됩니다.
노드 번호 1 2 3 4 5 6 거리 0 2 3 1 2 4 우선순위 큐 (거리:5, 노드: 3), (거리: 4, 노드: 3), (거리: 3 노드: 3), (거리: 4, 노드: 6) - [Step 3-5 ~ 3-8] 우선순위 큐에 있는 원소 중 가장 짧은 거리를 갖는 노드를 순차적으로 선택합니다.
- (거리: 3, 노드: 3) → 최단 경로가 업데이트 되지 않습니다.
- (거리: 4, 노드: 3) → 이미 방문했던 노드이므로 무시합니다.
- (거리: 4, 노드: 6) -> 최단 경로가 업데이트 되지 않습니다.
- (거리: 5, 노드 : 3) -> 이미 방문했던 노드이므로 무시합니다.
▶ 코드 구현
Python 코드로 구현하면 아래와 같습니다.
import heapq
#import sys
#input = sys.stdin.readline
INF = int(1e9)
n,m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF]*(n+1)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b,c))
def dijkstra(start):
q = []
heapq.heappush(q, (0,start)) ## (거리, 노드) ## q에 (0,start) 넣기
distance[start]=0
print(q)
while q:
dist, now = heapq.heappop(q)
### 이미 현재 노드가 처리된 적이 있는 경우
if distance[now] < dist:
continue
## 현재 노드와 인접한 다른 노드들 확인
for i in graph[now]:
cost = dist + i[1]
## 현재 노드를 거쳐서 다른 노드로 이동하는 거리가더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost,i[0]))
dijkstra(start)
for i in range(1,n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
2. 플로이드 워셜 알고리즘
플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우에 사용되는 최단 경로 알고리즘입니다.
각 단계에서 해당 노드를 거쳐가는 경우를 고려합니다.
- 예를 들어, 1번 노드에 대해서 확인할 때,
A → B의 비용과 A → 1 → B의 비용을 비교하여 A → 1 → B의 비용이 더 작은 경우 최단 경로 테이블을 업데이트합니다.
즉, N개의 노드에 대해서
각 단계에서 (N-1)개의 노드 중에서 서로 다른 노드 (A,B)를 선택합니다.
우리가 고려하는 그래프는 방향성이 있는 그래프 이므로 각 단계별로 총 $_{N-2}P_{2}$에 대해서 고려해야 합니다.
▶ 점화식
프롤이드 워셜 알고리즘은 식 $(1)$과 같이 점화식을 유도할 수 있습니다.
$$D_{ab} = min(D_{ab}, D_{ak} + D_{kb}) \tag{1}$$
점화식을 보면 a에서 b로 가는 최단 경로를 구할 때,
a에서 b로 다이렉트로 가는 경우와 a에서 k를 거쳐 b로 가는 경우 중 최솟값을 반영하는 것을 알 수 있습니다.
▶ Example
- [Step 0] 초기 상태: '연결된 간선'에 대해서는 단순히 그 값을 채워 넣고, 연결되지 않은 간선은 '무한'이라는 값을 넣습니다. (ex $D_{12} = 4, D_{13} = \text{INF}$)
- [Step 1] 1번 노드를 거쳐가는 경우 → 고려해야 하는 경우의 수 $_{3}P_{2} = 6$
$$D_{23} = min(D_{23}, D_{21} +D_{13})$$
$$D_{24} = min(D_{24}, D_{21} +D_{14})$$
$$D_{34} = min(D_{34}, D_{31} +D_{14})$$
$$D_{32} = min(D_{32}, D_{31} +D_{12})$$
$$D_{42} = min(D_{42}, D_{41} +D_{12})$$
$$D_{43} = min(D_{43}, D_{41} +D_{13})$$
- [Step 2] 2번 노드를 거쳐가는 경우 → 고려해야 하는 경우의 수 $_{3}P_{2} = 6$
- [Step 3] 3번 노드를 거쳐가는 경우 → 고려해야 하는 경우의 수 $_{3}P_{2} = 6$
- [Step 4] 4번 노드를 거쳐가는 경우 → 고려해야 하는 경우의 수 $_{3}P_{2} = 6$
▶ 코드 구현: 3중 반복문 사용
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]
for a in range(1,n+1):
for b in range(1,n+1):
if a==b:
graph[a][b]=0
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
for k in range(1,n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b]==INF:
print("INFITY", end=" ")
else:
print(graph[a][b], end =" ")
print()'Coding Study' 카테고리의 다른 글
| [##프로그래머스 & 백준 coding study ## : 2024.07] (0) | 2024.07.08 |
|---|---|
| [##프로그래머스 & 백준 coding study ## : 2024.06] (1) | 2024.06.03 |
| [## 프로그래머스 & 백준 coding study ##: 2024.05] (1) | 2024.05.31 |
| Depth First Search(DFS) & Breath First Search(BFS) (0) | 2024.05.14 |
| [## 프로그래머스 coding study ##: 2024.04] (0) | 2024.04.01 |
